Theory of Computation
CSE · Midterm · Fall 24
Batch 64
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 Semester Examination, Fall 2024
Course Code: CSE228, Course Title: Theory of Computation
Level: L2 Term: T2 Batch: 64
Time: 01.5 Hrs
Marks: 25
Answer ALL Questions
[All portions of each question must be answered sequentially.]
Q1 a) Summarize the difference between phi and epsilon. Given the Alphabet Sigma = {y, z, 0}, so compute Sigma^2 [2]
Q1 b) Evaluate the string 00110 using extended transition function for the following transition table. [2]
State | 0 | 1
-> q0 | {q0} | {q0, q1}
q1 | {q2} | phi
* q2 | phi | phi
Q1 c) Summarize the meaning of "a*b+b*a". [1]
Q2 a) Apply the knowledge of NFA to Design NFA's accepting the following languages over the alphabet {a,b}
i) The set of all Strings containing aba anywhere in the string
ii) The set of all Strings ending with bba
iii) ending with bbb [3]
Q2 b) Apply the knowledge of DFA to Design DFA's accepting the following languages over the alphabet {0,1}
i) The set of strings containing 010 at the end in the string
ii) Design DFA to accept the following language, L={W/ W has odd number of 1's and even number of 0's} [3]
Q2 c) Considering the transition table from the Q1 b. If the mentioned Automata is NFA, then convert to DFA. [4]
Q3 a) Construct the Regular Expression for the language consisting of all the strings of 0' and 1's that have the following condition:
i) Containing 110 anywhere in the string ii) Containing 1 either two or three possible position from the beginning. iii) Containing 101 at the end of the string [3]
Q3 b) Convert the following Regular expression (RE) into NFA with epsilon transition.
i) 1(1+0)*0 ii) (a|b)*(abb|a*b) [3]
Q3 c) Convert the following NFA into equivalent RE
[Figure: A state diagram with states 0, 1, 2, and 3. State 0 is the start state with a self-loop on a,b. From state 0 to state 1 on input a. From state 1 to state 2 on input a,b. State 2 is an accepting state. From state 2 to state 3 on input a,b. State 3 is an accepting state.] [4]