Theory of Computation
CSE · Final · Spring 26
Paper 2 of 2Batch 67 · ALI JAHAN RIASHADSwitch
Batch 67
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, Spring 2026
Course Code: CSE228, Course Title: Theory of Computation
Level: 2 Term: 2 Batch: 67
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.]
1. a) Consider the following CFG:
S -> S-S | S/S | (S) | ID
ID -> a | b | c | ID2 | ID3
Given string (a2-b3)/(c+a23)
i. Perform (LMD and RMD) for the given string.
ii. Construct the parse tree for the string.
iii. Determine whether the grammar is ambiguous or not. [2+2+1] CO3
b) A company stores logs where:
i. Every login (L) must have a matching logout (O)
Any number of error messages (E) may appear in between
Construct CFG and Show derivation of: LLEEOO
ii. Derive the following regular expression into CFG: 10 (10 + 1)* (0 + 11)* [3+2]
2. Consider the following CFG:
S -> Aba | bB | ε
A -> aA | BC | CD
B -> bB | ε | b
C -> D | Ab | ε
F -> d | S
Perform the following steps:
i) Eliminate null 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] CO3
3. a) Suppose You are designing a syntax checker for a programming language.
The language allows expressions of the form:
id^ $S id^
Where: id = identifier (a,b) $ = separator
*Number of identifiers before and after $ must be equal
Illustrate the Pushdown Automata for this language [5] CO4
b) Transition Function (δ):
1. δ(q0, a, Z0) = (q0, AZ0)
2. δ(q0, a, A) = (q0, AA)
3. δ(q0, b, A) = (q1, ε)
4. δ(q1, b, A) = (q1, ε)
5. δ(q1, b, Z_0) = (q2, BZ0)
6. δ(q2, b, B) = (q2, BB)
7. δ(q2, c, B) = (q3, ε)
8. δ(q3, c, B) = (q3, ε)
9. δ(q3, ε, Z0) = (qf, Z0)
i) Analyze the language accepted by the PDA.
ii) Verify whether the following string is accepted or rejected. Show all steps using Instantaneous Descriptions (ID):
(w = aaabbbcc, aaabbccc) [2+3]
4. a) Use Pumping Lemma for CFL to prove:
L = { a^i b^j c^k | i < j < k } is not a CFL. [5] CO4
b) Illustrate Turing machine to recognize the language, L = { 0^n 1^(3n) 2^(3n), n >= 1 }. [5]