Theory of Computing
SWE · Midterm · Spring 25
Paper 2 of 2By Sabbir HRSwitch
Paper 2 of 2
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
Midterm Examination, Spring 2025
Course Code: SE234 ; Course Title: Theory of Computing
Sections & Teachers: FBR (A,B,C,D), FJT (E, F, G, H) , RJM (I)
Time: 1 Hour 30 Mins | Marks: 25
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) Identify the difference between epsilon and phi with a finite automata diagram. Compare and contrast the advantages and disadvantages of Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) in terms of implementation and design. | [Marks-3] | CLO-1 Level-3
b) Construct Deterministic finite Automata for following language:
i) {w | every odd position of w is a 1 for binary alphabet}
ii) Let Sigma = {a, b} and let L = {ababa}. Design a DFA for L | [Marks-4]
c) Demonstrate the following finite automata and identify it. Also show epsilon/ empty string acceptance for provided finite automata. | [Marks-3] | [Figure: A finite automata diagram with states S0, S1, and S2, transitions with 0 and 1]
2. a) Use formal definition to precisely identify the following automata, and demonstrate computation for the string "0000.". | [Marks-3] | CLO-2 Level-3 | [Figure: NFA diagram with states q0, q1, q2 and transitions 0, 1]
b) Apply “Subset construction” method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- | [Marks-4] | [Figure: NFA diagram for subset construction]
c) Sketch a non-deterministic finite automata which accept a string containing “the” anywhere in a string of {a-z}, e.g., “there” but not “those” | [Marks-3]
3. a) Mention real life applications of Regular expression | [Marks-2] | CLO-3 Level-3
b) Construct Regular Expression for the following Language: L= {w| w does contain 3 consecutive b’s where alphabet in {b, d}} | [Marks-3]