Theory of Computation
CSE · Final · Fall 24
Paper 1 of 2Batch 64 · Md. Nur Hossain RhedoySwitch
Batch 64
Paper 1 of 2
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Faculty of Science & Information Technology
Department of Computer Science & Engineering
Final Examination, Fall 2024
Course Code: CSE228, Course Title: Theory of Computation
Level: L2 Term: T2 Batch: 64
Time: 02:00 Hrs
Marks: 40
Answer ALL Questions
[The figures in the right margin indicate the full marks and corresponding course outcomes.
All portions of each question must be answered sequentially.]
Q1 a) Consider the following CFG:
P -> ABCD
A -> aAA | cC | oD | iC
B -> ov | ovC
C -> id | id-D | e
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Experiment the above CFG to find out if the above mentioned CFG is ambiguous or not for the string covid-19. [3] CO2
b) Apply the concept of Push Down Automata (PDA) to accepts the language over alphabet {0,1,c}: L = {wcw^R, where w^R is the reverse of w and w in {0+1}*}.
After designing the PDA, Experiment the validity of the string 10011c11001 [7] CO2
Q2 a) Consider the following CFG:
S -> OSS | A, O -> + | * | /, A -> a | b | c
Analyze this CFG for the string +a * b /ca to Perform the Left most derivation, Right most derivation, also Generate Parse Tree [5] CO3
b) Drive the following regular expression into CFG: 0*10(0+1)*
Using the generated CFG:
Discover whether the strings 101001, and 011010, are accepted or not accepted. [5] CO3
Q3 Consider the following grammar:
S -> ASB
A -> aASAB | a | e
B -> SbS | A | bb
Perform the following steps:
i) Eliminate useless symbols from the grammar.
ii) Remove unit productions from the grammar.
iii) Eliminate epsilon (e)-productions from the grammar.
iv) Convert the resulting grammar into Chomsky Normal Form (CNF). [10] CO3
Q4 a) Propose the Pumping Lemma for the language A = {a^ib^i | i,j >= 0} is not regular. [5] CO4
b) Determine a Turing Machine which recognizes the languages L = {a^nb^2n | n >= 1} [5] CO4