Theory of Computation
CSE · Final · Fall 24
Paper 2 of 2Batch 64 · Robiul Karim JesanSwitch
Batch 64
Paper 2 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 -> aA | 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.
Marks: [3] | CO2
Q1(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
Marks: [7] | CO2
Q2(a) Consider the following CFG:
S -> O S S | 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
Marks: [5] | CO3
Q2(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.
Marks: [5] | CO3
Q3 Consider the following grammar:
S -> ASB
A -> aASAB | a | c
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).
Marks: [10] | CO3
Q4(a) Propose the Pumping Lemma for the language A = {a^j b^j | j>=0} is not regular.
Marks: [5] | CO4
Q4(b) Determine a Turing Machine which recognizes the languages L = { a^n b^2n | n>= 1 }
Marks: [5] | CO4