Skip to content

Theory of Computing

SWE · Final · Summer 26

Paper 3 of 5By Jobair HossainSwitch

Paper 3 of 5

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 Software Engineering Final Examination, Summer 2026 Course Code: SE234 Course Title: Theory of Computing Sections & Teachers: DDK (A-C), KRY (D, N-O), SHN (E-H), AMR (I-L), AAA (M) Time: 2: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) Demonstrate the regular language for the following expression and show one supported and one not supported string: i. 1* (011)* ii. (0+1)* 1 (0+1) (0+1) [Marks-2+2=4] [CLO-3, Level-3] b) Construct an e-NFA equivalent to the following regular expression using the lemma method. R = (0+1)* + (01+10)* [Marks-6] c) Construct a context-free grammar (CFG) for the following language: L = {ab^c^m d^n+m | n, m ≥ 0} [Marks-4] d) Show the Leftmost derivation and then construct a Parse Tree for the string aabqbba using the following context-free grammar: S -> aB | bA A -> a | aS | bAA B -> b | bS | aBB [Marks-3+3=6] e) Consider the following context-free grammar: S -> AB | C A -> aA | a B -> aB | b C -> aCb | ab Examine whether it is ambiguous by considering the string aaaqqb. [Marks-5] f) Construct a Pushdown Automata (PDA) that accepts the following language: L = {wcw^R | w ∈ {a, b}* }, where w^R denotes the reverse of w. Clearly show the state diagram and transition functions of the PDA. [Marks-6] g) For the PDA constructed in Question 1(f), trace the input string abbacbabba by showing the current state, remaining input, and stack content after each transition. [Marks-4] 2. a) Provide the formal definition of a Turing Machine as a 7-tuple and briefly explain each component. [Marks-2] [CLO-4, Level-3] b) Draw and label the basic components of a Turing Machine, and briefly describe the function of each component. [Marks-3]