Theory of Computing
SWE · Final · Spring 26
Paper 3 of 3By Md. Ferdous Foysal HridoySwitch
Paper 3 of 3
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, Spring 2026
Course Code: SE234; Course Title: Theory of Computing
Sections & Teachers: FJT(A-D), TM(E), FBR (F-J)
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:
(0+1)(0+1)*1(0+1)(0+1) | [Marks-3]
CLO-3
Level-3
b) Discover Regular Expression for the following languages over {0,1}
i. L={w|w starts with 0 and has odd length or ends with 1 and has even length}
ii. L={w|w has exactly one occurrence of 0} | [Marks-5]
c) Apply state elimination method to discover the Regular expression from the following DFA
[Figure: A DFA with states q0, q1, and q2. From q0, transition on 'a' goes to q1, and transition on 'b' goes to q2. State q1 has a self-loop on 'a,b'. State q2 has a self-loop on 'a,b'.] | [Marks-5]
d) Construct context free grammars to accept the following languages.
i) L={w|w is a binary string such that the number of 0's in w is divisible by 3}
ii) L={w|w is a odd length palindrome over the alphabet {x,y}} | [Marks-5]
e) S -> aB | bA
A -> a | aS | bAA
B -> b | bS | AB | [Marks-5]
i. Construct a Parse tree by showing LMD for the string aabbabba following the above CFG grammar.
ii. Prove that the grammar is ambiguous or not?
f) Illustrate a Non deterministic finite automata for the following regular expression by using the Lemma method.
((a+b)(c+d)*) + (a*bc*) | [Marks-5]
g) Context-free grammar for the Language L
S -> AB
A -> aAb | ab
B -> cBd | cd
Construct a Pushdown Automaton (PDA) that recognizes the language L.
Specify the transition functions of the PDA.
Demonstrate how the PDA processes the input string aaabbbccdd,
showing the sequence of transitions including stack operation. | [Marks-7]
2. a) Picture a Turing Machine graphically over Sigma = {a,b} for the language, L= {a^n b^n | n >= 1} | [Marks-3]
CLO-4
Level-3
b) Turing machines are abstract computational models used to determine which problems can be solved algorithmically
Describe the working principle of a Turing machine in detail, including its components and step-by-step execution process. | [Marks-2]