Skip to content

Theory of Computation

CSE · Midterm · Fall 24

Batch 64

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