COLLEGE OF VOCATIONAL STUDIES
DEPARTMENT OF COMPUTER SCIENCE
ASSIGNMENT: -BSc.(H)Comp. Sc. Semester:V NOV 2024
SUBJECT: TOC Maximum Marks: -12 Due Date: -14/11/2024
Instructions for the Candidate:
1. Write your Course, Roll No, Date, Paper Name and Semester on top of your answer
sheet
2. Attempt all questions. Hard copy submission is mandatory on due date.
3. Solutions must be given in step-by-step procedure wherever applicable.
Q.No:-
1) Construct a CFG for the language defined by regular expression (ab+ba)*
2) Construct PDA for the language L={ambncp m=n or n=p}
3) 1 Construct a regular expression and corresponding deterministic finite automaton (DFA)
defining a language comprising all strings of length 5 or more such that the letter appearing just
before the last is same as the second letter of the string.
4) Consider the following context free grammar (CFG):
S→0 𝐴 0 | 1 𝐵 1 | 𝐵 𝐵
A→𝐶
B→𝑆 | 𝐴
C→𝑆 | ∈
Eliminate ∈− productions, followed by the elimination of unit productions, and then remove all
the useless symbols. Also, put the resultant grammar into Chomsky Normal Form (CNF). Here,
∈ represents the null string.
5) Build FA for the following regular languages L1 and L2
L1= b(a+b)* L2 = a* b*
