Theory of Computation
CSE · Midterm · Spring 26
Paper 1 of 7Batch 67 · Ahnab ShariarSwitch
Batch 67
Paper 1 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 Tem Examination, Spring 2026
Course Code: CSE228, Course Title: Theory of Computation
Level:2 Term:2 Batch :67
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) Consider the alphabet set, Sigma = {x, y}.
i) Compute Sigma^4. How many strings can be generated if someone wants to generate only 5 length strings? [2]
b) Evaluate the string "abbab" using the extended transition function for the following NFA.
Transition table (delta):
States | a | b
->p | {p, q} | {p}
q | {r} | {r}
r | {s} | empty set
*s | {s} | {s}
[2]
CO1
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]
CO2
b) Apply the knowledge of DFAtoshop 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.
[3+2]
ii)The set of strings containing the substring aba or bab anywhere.
C) Apply the knowledge of conversion NFA to DFA, convert the NFA in the given 1(b), into DFA.
[3]
3. 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 is element of {a, b} | The 3rd symbol from the left is b}.
[3]
CO2
b) Convert the RE into NFA with epsilon transition:
i. (a+b)*(abb+a*b)
ii. ((ba*)+a*b)*abb
[4]
C) [Figure: State diagram of a finite automaton with states q1, q2, q3, transitions on 0 and 1, starting at q1]
Convert the above DFA into equivalent RE.
[3]