Theory of Computation

Daffodil International University Faculty of Science & Information Technology Department of Computer Science & Engineering Mid Term Examination, Fall 2026 Course Code: CSE228, Course Title: Theory of Computation Batch: 68 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, Σ = {a, b,c}. i) Explain the meaning of Σ^2 by generating the corresponding strings. (ii) Describe the difference between an alphabet set and a language. [2] b) Interpret the string "00111" using the extended transition function for the following NFA. Transition table (δ): States | 0 | 1 ->A | {A,B} | {A} B | {C} | {C} C | {D} | ∅ *D | {D} | {D} [3] 2. a) Apply the knowledge of NFA to to design NFA's for the following: (i) To recognize the following set of strings: {0101, 101,011} over the alphabet set {0,1}. (ii) L={W|W ends with ab or bab} over the alphabet Σ={a,b}. [2] b) Apply the knowledge of DFA to design DFA's for the following: i) L={W | W has an even number of a's or an odd number of b's} over the alphabet Σ={a,b}. ii )The set of all strings that do not contain 00 over the binary alphabet Σ={0,1}. (iii) To verify employee ID's ranging from FACULTY-001 to FACULTY-982 of Daffodil International University. The DFA should accept all valid employee ID's within this range and reject ID's below FACULTY-001 or above FACULTY-982. Construct only the DFA transition diagram. [5] c) (i)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 {0, 1}: i) The set of all strings that contain that start with 0 and end with 01. ii) The set of all strings that contain 1011 as a substring in the middle. iii) The set of all strings where the number of 1's is divisible by three. [3] b) Convert the RE into NFA with ε transition over the alphabet set {a,b}: i. (a+b)*bab* ii. ((ba*)*+a)*bb [3] c) [Figure: DFA state diagram with states s0 (start), s1, s2 (accepting), s3] Convert the above DFA into equivalent RE. [4]