Theory of Computing
SWE · Final · Summer 26
Paper 2 of 5By SIFAT SHAHARIA -43Switch
Paper 2 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:
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)* + (0+10)*
[Marks: 6]
c) Construct a context-free grammar (CFG) for the following language:
L = {a^b^c^m d^n+m+1 | n, m ≥ 0}
[Marks: 4]
d) Show the Leftmost derivation and then construct a Parse Tree for the string aabbabba 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 aaaaab.
[Marks: 5]
f) Construct a Pushdown Automata (PDA) that accepts the following language:
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.
[Marks: 6]
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]