Skip to content

Theory of Computation

CSE · Midterm · Spring 26

Paper 1 of 7Batch 67 · Ahnab ShariarSwitch

Batch 67

Paper 1 of 7

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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]