Skip to content

Theory of Computation

CSE · Final · Fall 25

Batch 66

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, Fall 2025 Course Code: CSE228, Course Title: Theory of Computation Level: L2 Term: T2 Batch: 66 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 Context Free Grammar (CFG): S -> SS | O | T O -> + | - | * | / T -> x | y | z Analyze the given CFG for the input string : xy- yxz + */ Perform the following i) Leftmost Derivation ii) Rightmost Derivation iii) Based on both derivations, infer whether the grammar is ambiguous or unambiguous for this input string with parse tree. [6] CO3 b) i) Design a set of production rules for a language that generates strings over {a, b} where the number of a's is equal to the number of b's. [4] ii) Drive the following regular expression into CFG: 0*101(0+1)* Q2 Consider the following CFG: S -> AB | aS | B A -> aA | ̄ B -> bB | C C -> a | ̄ D -> dD For the given grammar, perform the following transformations: i) Eliminate all epsilon (̄) productions. ii) Remove all unit productions from the grammar. iii) Identify and eliminate all useless symbols. iv) Convert the simplified grammar into Chomsky Normal Form (CNF). [10] CO3 Q3 a) Determine, with proper evaluation and justification, whether the following language is regular or not using Pumping Lemma: L = {x^n y^2n | n >= 1} [5] CO4 b) Design a Turing Machine that recognizes the language L = {x^n y^2n z^n | n >= 1} [5] Q4 a) After designing the Push Down Automata (PDA) for the Language, L = {a^3n b^n | n >= 1}, evaluate that for the string "aaaaaaaaabbb" is accepted or not in PDA. [6] CO4 b) Consider the following PDA: P = ({q0, q1, q2, q3, q4, f}, {0,1}, {Z0, A, B}, ̄, q0, Z0, {f}). The transition functions are given below: 1. ̄(q0, 0, Z0) = (q1, AAZ0) 2. ̄(q1, 0, A) = (q1, AAA) 3. ̄(q2, 0, B) = (q3, ̄) 4. ̄(q3, ̄, B) = (q2, ̄) 5. ̄(q0, 1, Z0) = (q2, BZ0) 6. ̄(q1, 1, A) = (q1, ̄) 7. ̄(q2, 1, B) = (q2, BB) 8. ̄(q3, ̄, Z0) = (q1, AZ0) 9. ̄(q0, ̄, Z0) = (f, ̄) 10. ̄(q1, ̄, Z0) = (q0, Z0) 11. ̄(q2, ̄, Z0) = (q0, Z0) 12. ̄(q3, 1, Z0) = (q2, BZ0) Evaluate the execution of the given PDA and provide the sequence of Instantaneous Descriptions (IDs) to demonstrate that the strings "101" and "011" are accepted or not accepted by L(P). [4]