Theory of Computing
SWE · Midterm · Summer 26
Paper 1 of 2Section A-OSwitch
Section A-O
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, Summer 2026
Course Code: SE234 Course Title: Theory of Computing
Sections & Teachers: DDK (A-C), KRY (D, N-O), SHN (E-H), AMR (I-L), AAA (M)
Time: 1:30 Hrs
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) Model a Deterministic Finite Automaton (DFA) over E={a, b} for the language -
L = {w | w starts with ab and ends with ba}.
Show both the state diagram and the transition table. [Marks-5]
b) Diagram a Deterministic Finite Automaton (DFA) over E={0, 1} for the language -
L = {w | w contains exactly two 1's}. [Marks-3]
c) [Figure: A DFA state diagram with states q0, q1, q2, q3. Transitions: q0 -> q1 on a, q0 -> q3 on b, q1 -> q1 on a, q1 -> q2 on b, q2 -> q1 on a, q2 -> q- (unlabeled) on b, q3 -> q3 on a, b. Wait, looking closer: q0 has loop? No, q0 to q1 on a, q0 to q3 on b. q1 to q1 on a, q1 to q2 on b. q2 to q1 on a, q2 to q2 on b? No, q2 loops on b? q2 has transition to q1 on a, and... Let's use generic description: [Figure: DFA state diagram with states q0, q1, q2, q3]]
Trace the computation of the above DFA for each of the following strings and confirm whether each string is accepted or rejected. [Marks-2]
i. abbaba
ii. abbaaab
2. a) Model a Non-deterministic Finite Automaton (NFA) over E={a, b} for the language -
L = {w | w where every a should be followed by bb}.
Show both the state diagram and the transition table. [Marks-3]
b) Transform the following NFA into an equivalent DFA using the subset construction method. [Marks-7]
[Figure: NFA state diagram with states q0, q1, q2, q3. Transitions: q0 to q0 on a, b; q0 to q1 on a; q1 to q2 on a; q2 to q3 on b]
3. a) Derive a regular expression for the language
L = {w | w has an even number of a's}. [Marks-3]
b) Derive a regular expression for the language
L = {w | w contains any number of a's followed by any number of b's}. [Marks-2]