Skip to content

Theory of Computation

CSE · Final · Spring 26

Paper 2 of 2Batch 67 · ALI JAHAN RIASHADSwitch

Batch 67

Paper 2 of 2

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 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]