Home / Theory of Computation and Concrete Mathematics / Theory of Computation Questions

# Theory of Computation Questions

Define automata theory and describe how does it relates with CSE.

What is DFA? Describe how does DFA process srtings.

Covert the following NFA to its equivalent DFA.

Briefly describe the equivalence of Deterministic and Nondeterministic finite automata.

Contruct a  DFA which accepts the set of all strings over {0,1}, where each string contains the substring 1010.

Contruct a  DFA which accepts the set of all strings over {x,y}, where each string contains the substring symbol.

Define regular expression with its application.

Describe the building procedure of regular expressions.

Convert the following FA to a rgular expression.

Prove that, if every language is defined by a regular expression, then it is also defined by a finite automaton.

Describe the conversion techniques from FA to regular expressions.

Convert the regular expression (0+1)*1(0+1) to a e-NFA.