1.a. Construct DFA for language defined by where

S = ( string containing only a's)

S = (string containing only b's)

S = ( string containing only a's or b's)

1.b. Explain the application of Regular expression in Text search and Replace

1.c. Write short on

i) Chomsky Normal Form

ii) Greibach Normal Form

2.a. with respect to properties of regular language explain whats is pumping lemma and closure properties of regular languages

1.c. State significance of normalization process of grammar.

Let G be a CFG with productions

Convert G in CNF.

3.a. Define Turing machine. Explain recursively enumerable sets.

3.b. Write short notes on -

i) Non Deterministic TM

ii) Composite TM

iii) Halting problem of TM

3.c. Obtain Turing Machine to accept a language

4.a. Explain the Representation of TM

4.b. Construct TM for 1's compliment of binary number.

4.c. Design the Turing machine to accept the language

containing the substring 001.

5.a. Define PDA. What are the different types of PDA?

5.b. Design a PDA that accepts

5.c. Construct a PDA that accepts all palindrome string over . Specify simulation for string ába'.

6.a. Explain the working of Top-Down parser with example.

6.b. Constructs a PDA that recognizes the language accepted by following DFA.

6.c. Construct a NPDA that accepts the language

7.a. What do you mean by NP-problems? Justify that Travelling salesman problem is NP problem.

7.b. Explain the vertex cover problem in the context of polynomial time reduction. Justify with suitable example.

8.a. Write short notes on

i) Undecidability

ii) Post Correspondence Problem

8.b. What is Universal Turing Machine ? Comment on stored program concept with reference to the same