Skip to content

Theory of Computing

SWE · Final · Summer 25

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 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