Theory of Computing
SWE · Midterm · Spring 26
Paper 2 of 2Section A-JSwitch
Section A-J
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 2026
Course Code: SE234; Course Title: Theory of Computing
Sections & Teachers: FJT(A-D), TM(E), FBR (F-J)
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) | Draw both a DFA and an NFA for the given language L = {w ∈ {0,1} | w contains substring "10"} and Illustrate how non determinism in an NFA can reduce the number of states compared to an equivalent DFA by constructing both machines for a simple language. | [Marks: 3] | CLO-1
Level-3
1. b) | Construct state diagram of Deterministic finite Automata for language
i) L = {w | w starts with 'a' and contains substring "bb" where input is {a,b}}
ii) L = {w ∈ {0,1} | number of 0's is divisible by 3} | [Marks: 4] |
1. c) | Demonstrate and identify the following Finite Automata and show epsilon acceptation and 0110101 string acceptance. [Figure: A finite automaton diagram with states q0, q1, q2, q3, transition arrows, and labels] | [Marks: 3] |
2. a) | Illustrate the advantages and disadvantages of Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) in terms of implementation, design, state complexity, memory usage. | [Marks: 3] | CLO-2
Level-3
2. b) | Apply subset construction method to convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)- [Figure: An NFA transition diagram with states q0, q1, q2 and transitions labeled a, b, a,b] | [Marks: 4] |
2. c) | Construct a Non deterministic finite automata where L = {w| w strings having 3rd symbol 'a' from right end where Σ = {a,b,c}} | [Marks: 3] |
3. a) | Express Regular Expression for the following Language:
L = {w| w where each string should have three consecutive b's for input {b,c}}
How regular expressions represent patterns in formal languages and evaluate their effectiveness by constructing one example and explaining how it captures the structure of the language? | [Marks: 5] | CLO-3
Level-3