Theory of Computation
CSE · Midterm · Spring 25
Batch 65
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