Skip to content

Theory of Computation

CSE · Midterm · Fall 25

Batch 66

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 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]