Theory of Computation
CSE · Final · Spring 25
Batch 65
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, Spring 2025
Course Code: CSE228, Course Title: Theory of Computation
Level: L2 Term: T2 Batch: 65
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) Apply the concept of Pushdown Automata (PDA) to discover a PDA that accepts the language L = {0^n 1^(2n) | n >= 1} and Analyze that the string 000111111 is accepted [6] CO3
b) Consider the following PDA:
P = ({q0, q1, q2, q3, q4, f}, {a,b}, {Z0, A, B}, δ, q0, Z0, {f}).
The transition functions are given below:
1. δ (q0, a, Z0) = (q1, AAZ0)
2. δ (q1, a, A) = (q1, AAA)
3. δ (q2, a, B) = (q3, ε)
4. δ (q3, ε, B) = (q2, ε)
5. δ (q0, b, Z0) = (q2, BZ0)
6. δ (q1, b, A) = (q1, ε)
7. δ (q2, b, B) = (q2, BB)
8. δ (q3, ε, Z0) = (q1, AZ0)
9. δ (q0, ε, Z0) = (f, ε)
10. δ (q1, ε, Z0) = (q0, Z0)
11. δ (q2, ε, Z0) = (q0, Z0)
12. δ (q3, b, Z0) = (q2, BZ0)
Analyze the execution of the given PDA and provide the sequence of Instantaneous Descriptions (IDs) to demonstrate that the strings "bab" and "abb" are accepted by L(P). [4] CO3
Q2 a) Consider the following CFG:
E -> I / E+E / E*E / (E), I -> a / b / Ia / Ib / I0 / I1
Analyze the given CFG for the string (b+a11)+(b0+a00) by performing Leftmost Derivation, Rightmost Derivation. Also, infer whether the above-mentioned CFG is ambiguous or not for the above strings. [5] CO3
b) Convert the given regular expression (a+b)*bab* into CFG
Using the generated CFG, determine whether the following strings are accepted: abbabb, and babbb [5] CO3
Q3 Consider the following grammar:
S -> AX | B | ε
A -> AS | ε
B -> bA | C
C -> cB | ε
X -> aB | b
Determine the following steps:
i) Eliminate epsilon (ε)-productions from the grammar.
ii) Remove unit productions from the grammar.
iii) Eliminate useless symbols from the grammar.
iv) Convert the resulting grammar into Chomsky Normal Form (CNF). [10] CO4
Q4 a) Determine that the language L = {0^(n)1^(n) | n>=1} is not regular by using pumping lemma [5] CO4
b) Design a Turing Machine which recognizes the language L = {a^n b^n c^n | n >= 1} [5] CO4