Theory of Computation
CSE · Quiz · Fall 25
Paper 2 of 3By Md. Ferdous Foysal Hridoy (1)Switch
Paper 2 of 3
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
a) Apply the knowledge of Regular Expression (RE) to the RE accepting the following languages:
i) Start with xyz or ending with xyy over Σ={x,y,z}
ii) Contain at least one occurrence of 123 anywhere in the string, Σ={0,1,2,3}
b) Convert the following Regular Expression (RE) into an ε-NFA (Epsilon Non-deterministic Finite Automaton):
Regular Expression: (0 + 1)* 01*+(01)*
c) Convert the following DFA into RE by state elimination approaches:
States | 0 | 1
-> q0 | q1 | q0
q1 | q1 | q2
* q2 | q2 | q2