Theory of Computation
CSE · Final · Spring 26
Paper 1 of 2Batch 67 · Ahnab ShariarSwitch
Batch 67
Paper 1 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|$+S
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
1. 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 + 1)* | [3+2]
2. Consider the following CFG:
S -> Aba | bB | e
A -> aA | BC | CD
B -> bB | e | b
C -> D | Ab | e
D -> d | S
Perform the following steps:
i. Eliminate null productions(e) 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
3. b) Transition Function (d):
1. d(q0, a, Z0) = (q0, AZ0)
2. d(q0, a, A) = (q0, AA)
3. d(q0, b, A) = (q1, e)
4. d(q1, b, A) = (q1, e)
5. d(q1, b, Z_0) = (q2, BZ0)
6. d(q2, b, B) = (q2, BB)
7. d(q2, c, B) = (q3, e)
8. d(q3, c, B) = (q3, e)
9. d(q3, e, 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 = aaabbbbcc, aaabbbccc) | [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
4. b) Illustrate Turing machine to recognize the language, L= { 0^n 1^3n 2^3n, n >= 1 }. | [5]