Theory of Computation
CSE · Midterm · Spring 26
Paper 7 of 7Batch 67 · AbdullahSwitch
Batch 67
Paper 7 of 7
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 Computer Science & Engineering
Mid Term Examination, Spring 2026
Course Code: CSE228, Course Title: Theory of Computation
Time: 1:30 Hrs
Level: 2 Term: 2 Batch: 67
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) Consider the alphabet set, ΅ = {x, y}.
i) Compute ΅^4. How many strings can be generated if someone wants to generate only 5 length strings?
[2]
1. b) Evaluate the string "abbab" using the extended transition function for the following NFA.
Transition table (Δ):
States | a | b
->p | {p,q} | {p}
q | {r} | {r}
r | {s} | ∅
*s | {s} | {s}
[2]
2. a) i) Design a NFA over the alphabet {0, 1} that accepts all strings that contain at least one 0 and at most two 1's.
ii) Design a NFA that accepts strings over the alphabet {a, b, c} that contain at most 4 occurrences of b.
iii) Give a NFA accepting the following language over the alphabet {0, 1}: the set of strings that end with ba, bb and baa.
[3]
2. b) Apply the knowledge of DFA to design DFA's for the following:
i) A new MRT ticket-vending machine is being designed that issues a ticket only when exactly Tk 25 has been inserted, and accepts only note denominations of 5 taka, 10 taka, or 25 taka. The machine is automated using a deterministic finite automaton. If at any step the cumulative amount inserted would exceed 25, the machine should move to a "trap" (dead) state and never issue a ticket. If the insertion ends with a total less than 25, the machine should reject the ticket. Only sequences of note insertions whose sum is exactly 25 should lead to acceptance.
ii) The set of strings containing the substring aba or bab anywhere.
[3+2]
3. c) Apply the knowledge of conversion NFA to DFA, convert the NFA in the given 1(b), into DFA.
[3]
4. a) Construct the regular expressions for the following languages over {a, b}:
i) The set of all even length strings that contain exactly two b's.
ii) The set of all strings that contain the substring aba and the substring bab.
iii) L = {w ∈ {a,b}* | The 3rd symbol from the left is b}.
[3]
4. b) Convert the RE into NFA with Ε transition:
i. (a+b)*(abb+a*b)
ii. ((ba*)+a*b)*abb
[4]
4. c) [Figure: A finite state machine diagram with states q1, q2, q3. State q1 has a self-loop with 0, and a transition to q2 with 1. State q2 has a self-loop with 1, a transition to q3 with 0, and a transition back to q1 with 0,1. State q3 has a self-loop with 0, and a transition to q2 with 0,1.]
Convert the above DFA into equivalent RE.
[3]