Skip to content

Theory of Computation

CSE · Final · Spring 25

Batch 65

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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