Theory of Computing
SWE · Midterm · Spring 25
Paper 1 of 2By SUPAN ROYSwitch
Paper 1 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 ε and Φ 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 = {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: DFA diagram with states S0, S1, S2, transitions 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]
b) Apply "Subset construction" method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- [Marks-4] [Figure: NFA diagram with q0, q1, q2]
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]