Theory of Computing
SWE · Midterm · Summer 26
Paper 2 of 2By Tonmoy Chandra MudiSwitch
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, 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 Sigma={a, b} for the language - | [Marks-5] | CLO-1
L = {w | w starts with ab and ends with ba}. | Level-4
Show both the state diagram and the transition table.
1. b) Diagram a Deterministic Finite Automaton (DFA) over Sigma={0, 1} for the language - | [Marks-3]
L = {w | w contains exactly two 1's}.
1. c) [Figure: A DFA state diagram with states q0, q1, q2, q3. q0 has transitions: 'a' to q1, 'b' to q3. q1 has transitions: 'a' to q1, 'b' to q2. q2 has transitions: 'a' to q1, 'b' to q2. q3 has transitions: 'a, b' to q3.] | [Marks-2]
Trace the computation of the above DFA for each of the following strings and confirm whether each string is accepted or rejected.
i. abbaba
ii. abbaaab
2. a) Model a Non-deterministic Finite Automaton (NFA) over Sigma={a, b} for the language | [Marks-3] | CLO-2
L = {w | where every a should be followed by bb}. | Level-4
Show both the state diagram and the transition table.
2. b) Transform the following NFA into an equivalent DFA using the subset construction method. | [Marks-7]
[Figure: An NFA state diagram with initial state q0 having an epsilon transition and a loop 'a, b' to q0, and transition 'a' to q1. q1 has transition 'a' to q2. q2 has transition 'b' to q3.]
3. a) Derive a regular expression for the language | [Marks-3] | CLO-3
L = {w | w has an even number of a's}. | Level-3
3. b) Derive a regular expression for the language | [Marks-2]
L = {w | w contains any number of a's followed by any number of b's}.