Theory of Computing
SWE · Final · Summer 26
Paper 5 of 5By Ahnab ShariarSwitch
Paper 5 of 5
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: [Marks - 2+2 = 4] CLO-3 Level-3
i. 1*(011*)*
ii. (0+1)* 1 (0+1) (0+1)
b) Construct an ε-NFA equivalent to the following regular expression using the lemma method. [Marks-6]
R = (0+11)* + (01+10)*
c) Construct a context-free grammar (CFG) for the following language: [Marks-4]
L = {ab^n c^m d^n+m+1 | n, m ≥ 0}
d) Show the Leftmost derivation and then construct a Parse Tree for the string aabbabba using the following context-free grammar: [Marks - 3+3=6]
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
e) Consider the following context-free grammar: [Marks-5]
S → AB | C
A → aA | a
B → aB | b
C → aCb | ab
Examine whether it is ambiguous by considering the string aaaaab.
f) Construct a Pushdown Automata (PDA) that accepts the following language: [Marks-6]
L = {w c w^R | w ∈ {a, b}* }, where w^R denotes the reverse of w.
Clearly show the state diagram and transition functions of the PDA.
g) For the PDA constructed in Question 1(f), trace the input string abbabcbabba 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]