Theory of Computing
SWE · Midterm · Spring 26
Paper 1 of 2By Sabbir HRSwitch
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 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 E {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 E {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. | [Marks- 3] | [Figure: NFA diagram with states q0, q1, q2, q3]
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)- | [Marks- 4] | [Figure: NFA diagram with states q0, q1, q2 and transitions with a, b]
2. c) Construct a Non deterministic finite automata where L = {w| w strings having 3rd symbol 'a' from right end where Sigma = {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