Construct the minimum state automata equivalent to the transition diagram.

<img src='./qimages/15490-1a.jpg'>

Show that the set L i is not regular.

Define the pumping-lemma for regular set and describe its application.

Design the DFA over to, for even number of and 1's.

Prove

Reduce the following grammar G in to CNF.

G aAD, A aB bAB, B D

Convert the grammar S AA A into Greibach Normal Form (GNF).

Show that L a^P is a prime} is not a context free language.

Design a pushdown automata for the language L a^n b^n 1

If a context free grammar is defined by the production S a |Sa |bSS |SSb show that every string in has more than b's.

Convert the grammar S aSb A bSA to a PDA that accepts the same language by empty stack.

Prove

Construct a DFA with reduced state equivalent to the regular expression 10 11)0*1.

Find the regular expression of the figure.

<img src='./qimages/15490-7a.jpg'>

Construct a grammar G generating the language L b^n 1}.

Define Turing Machine Model and give diagrammatic representation of Turing Machine.

Design a Turing Machine that accepts L b^n 1}.

Define variants of TM.

Define Decidability and Decidable language.

10. Attempt any two from the following:

Define Halting problem of TM.

State Church thesis.

What is CYK algorithm Design or construct a TM to accept the set L of all strings over ending with 010.