AL-601 - Theory of Computation

What is Moore Machine? How Moore machine can be converted into Mealy Machine? Explain with the help of an example.

Describe how Finite automata can be called a language acceptor?

Explain briefly about the composite machine with an example.

Find out the Regular Expression from given DFA.

What do you mean by Closure properties of regular languages? Define some important closure properties.

Obtain the regular expression for the following set: (i) Set of all strings over $\Sigma = \{a,b\}$ with exactly two $a$. (ii) $L = \{a^x \mid x \text{ is divisible by } 3 \text{ or } 5\}$.

Differentiate between Context-Free Grammar and Context-Sensitive Grammar.

Show that $L = \{a^n b^n c^n \mid n \ge 1\}$ is not CFL.

Write CFG for regular expression $(011 + 1)^*(01)^*$.

Design PDA to accept the language $L(G) = \{a^m b^n a^m \mid m,n \ge 1\}$.

Design a PDA which recognizes the set of all even length palindromes over $\{a, b\}$.

What is PDA? Explain instantaneous description of PDA.

Design a Turing Machine for the language $L(G) = \{a^n b^n \mid n \ge 1\}$.

Explain P class problems in detail.

Write short note on any two of the following: (i) NP Hard (ii) Petri Net Model (iii) Halting problem of Turing machine (iv) 2-way DFA.