Theory of Computation
CSE · Midterm · Fall 25
Batch 66
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, Fall 2025
Course Code: CSE228, Course Title: Theory of Computation
Level: L2 Term: T2 Batch: 66
Time: 01.5 Hrs
Marks:25
Answer ALL Questions
[All portions of each question must be answered sequentially.]
Q1 a) Summarize the difference between ∑* and ∑+. Let the Alphabet ∑={a, b, c}, so compute ∑^2
Marks: [2]
CO1
Q1 b) Evaluate the string 1001101 using the extended transition function for the following transition table.
State | 0 | 1
-> q0 | {q0} | {q0, q1}
q1 | {q2} | Ø
q2 | Ø | {q3}
*q3 | Ø | Ø
Marks: [3]
CO1
Q2 a) Apply the knowledge of NFA to Design NFA's accepting the following words: Batch66, CSE228, Dept, CSE, TOC
Marks: [3]
CO2
Q2 b) Apply the knowledge of DFA to Design DFA's for the following:
i) Design a DFA that recognizes valid product identifiers formatted as PRD-2XX (where XX ranges from 01-99), ensuring automated validation and rejection of invalid codes within an inventory management system.
ii) The set of strings containing 010 at the end in the string over alphabet {0,1}
iii) Language L={W/ W has odd number of 1's and odd number of 0's} over alphabet {0,1}
Marks: [4]
CO2
Q2 c) Apply the knowledge of conversion of NFA to DFA, convert the NFA given in Q1 b, to DFA
Marks: [3]
CO1
Q3 a) Construct the Regular Expression for the languages
i) Containing aba or bab anywhere in the string over the alphabet {a,b}
ii) Containing d either two or three possible positions from the beginning over the alphabet {b,d}.
iii) Containing 101 or 010 at the end of the string over the alphabet {0,1}
Marks: [3]
Q3 b) Convert the following Regular Expression (RE) into NFA with ε transition.
i) (a|b)*(ab|a*b)
ii) (ba*)*+bab
Marks: [3]
CO2
Q3 c) Using the State elimination approach, Convert the given NFA into its corresponding Regular Expression.
[Figure: NFA with states 0, 1, 2, 3 where state 0 is start, state 3 is final, with transitions labeled a,b between 0 and 0, a between 0 and 1, a,b between 1 and 2, and b between 2 and 3]
Marks: [4]