Theory of Computing
SWE · Midterm · Spring 23
Section A
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Department of Software Engineering
Faculty of Science & Information Technology
Midterm Examination, Spring 2023
Course Code: SE234 ; Course Title: Theory of Computing
Sections & Teachers: A (35 Batch) , A (36 Batch) & FBR
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 phi with finite automata diagram. [Marks-2] [CLO-1, Level-3]
b) Construct Deterministic finite Automata for following language: {w | every odd position of w is a 1 for binary alphabet}. II. Let Sigma = {a, b} and let L = {baa}. Design a DFA for L. [Marks-2.5+2.5] [CLO-1, Level-3]
c) Demonstrate the following DFA and show epsilon acceptance. [Figure: DFA with states q0, q1, q2 and transitions on a, b] [Marks-3] [CLO-1, Level-3]
2. a) Differentiate DFA and NFA by showing a proper example with diagram. [Marks-3] [CLO-2, Level-5]
b) Formulate subset construction method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- [Figure: NFA with states q0, q1, q2 and transitions] [Marks-4] [CLO-2, Level-5]
c) Construct a Non deterministic finite automata for input {a,b} where L = {w | w where any numbers of a's followed by any number of b's}. [Marks-3] [CLO-2, Level-5]
3. a) Explain Regular Expression and compare a* and a+. [Marks-3] [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,c}}. [Marks-2] [CLO-3, Level-3]