Skip to content

Theory of Computation

CSE · Midterm · Spring 25

Batch 65

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, Spring 2025 Course Code: CSE228, Course Title: Theory of Computation Level: L2 Term: T2 Batch: 65 Time: 01.5 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.] Q1 a) Summarize the difference between sigma^+ and sigma^* with an example. Given L = {a, bc}, so compute L^*. [2] | CO1 Q1 b) Identify which language represent by the following transition table as well as evaluate the string 00110 using extended transition function. State | 0 | 1 -> q0 | q0 | q1 q1 | q2 | q1 * q2 | q0 | q1 [2] | CO1 Q1 c) Summarize the meaning of (a+b)(a+b)a(a+b)*. [1] | CO1 Q2 a) Apply the knowledge of NFA to Design NFA's accepting the following languages: I. To recognize the following sets of strings: CSE228, BATCH65, SPRING2025. where sigma = {0,1,2...9, A,B,C...Z} II. To accept the set of strings that end with ba, bb and baa. where sigma = {a,b} [3] | CO2 Q2 b) Apply the knowledge of DFA to design DFAs to: i) Verify student IDs in the range 232-15-001 to 232-15-981 for the students of CSE Batch 65 at DIU, ensuring automated validation and error prevention in the university's system. ii) Recognizes binary strings ending with "101" [3 + 1] | CO2 Q2 c) Design a NFA for the binary strings that end with 10. After designing NFA, convert that to DFA. [3] | CO2 Q3 a) Construct a Regular Expression (RE) for the language consisting of all binary strings (0s and 1s) that satisfy the following conditions: i) Start with 10 and contain 011 anywhere in the string. ii) Have exactly two consecutive 1s in any position. iii) End with 00 or 11. [3] | CO2 Q3 b) Draw epsilon NFA for the following RE: i. (0+1)*1(0+1) ii. ((ba*)*+abb [3] | CO2 Q3 c) Convert the following DFA into equivalent RE by state elimination approach [Figure: A DFA diagram with states q0, q1, q2, q3. Transitions: q0 to q1 on 1, q1 to q2 on 0, q2 to q3 on 0, q3 to q3 on 0,1, q3 to q0 on 1, q1 to q0 on 0.] [4] | CO2