Theory of Computing
SWE · Final · Summer 25
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 2025
Course Code: SE234; Course Title: Theory of Computing
Sections & Teachers: FBR (A-D), FJT (E-H), NJN (I-J), ZNM (K-L), MMN (M), AMR (N)
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) Construct a Parse Tree (showing LMD) for the string abbababa using the CFG: S -> aSb | bSa | ab. | [Marks-3] CLO-3 Level-3
1. b) Apply state elimination method to discover the Regular expression from the following DFA To remove follow the order q0, q2, qf. | [Marks-5] [Figure: DFA with states q0, q1, q2, qf and transitions with a, b]
1. c) L1: Construct the regular expression for the language over {0,1} such that no two 1's occur consecutively.
L2: Construct a regular expression for the language consisting of one or more 0's followed by zero or more 1's followed by one or more 0's. | [Marks-5]
1. d) Illustrate a Non deterministic finite automata for the following regular expression by using the Lemma method. (ab* + ba*)*a. | [Marks-4]
1. e) i) Construct a Context Free Grammar (CFG) for the language: {w | w contains equal number of 0's and 1's}
ii) Construct a CFG for the language: L(G) = {a^b^2n c^m d^k | n >= 1, m > 1, k >= 0} | [Marks-5]
1. f) Apply the concept of grammar ambiguity to determine whether the given grammar is ambiguous or not.
S -> A | B
A -> aAb | ab
B -> abB | e | [Marks-4]
1. g) Construct a Push down Automata for the following language: L = {a^n b^n c^m | n, m >= 1}. | [Marks-4]
1. h) Demonstrate the following Push down automata and illustrate the acceptance (or rejection) of the string abaaba. | [Marks-5] [Figure: PDA transition diagram with states q0, q1, qf and stack operations]
2. a) Compare the expressive power of Finite State Machine (FSM), Context Free Language (CFL), and Turing Machine (TM) with suitable examples for each.
Also Show a Turing Machine over binary alphabet for L = {w|w ends with 101} | [Marks-5] CLO-4 Level-2