Theory of Computation
CSE · Final · Fall 25
Batch 66
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]