1.a. Define the following terms with example-

i) Alphabets

ii)String

iii)Regular Expression

1.b. Design a DFA which accepts a ternary number divisible by 4.

1.c. Design FA accepting the following language over the alphabet {0,1}

i) Set of all strings having at least three consecutive zeros.

ii) Set of all strings that begin and end with same symbol.

2.a. Define the following terms with example

i) DFA

ii) NFA

iii) NFA - $\epsilon$

2.b.

b) Eliminate the useless symbol in the grammer below-

S $\rightarrow$ aA|bB

A $\rightarrow$aA|a

B $\rightarrow$bB

D $\rightarrow$ab|Ea

E $\rightarrow$aC|d

2.c. Construct a DFA accepting the following language over the alphabet {a,b}

i) Set of all string that begin with substring ab.

ii) Set of all strings with at most two consecutive b's.

3.a. Write short notes on -

i) Universal Turing Machine

ii) Multi-tape Turing Machine

3.b Construct a Turing Machine for R = (a+b)*bb.

3.c. Construct a Turing Machine to accept the language

4.a. Write short notes on -

i) Unsolvable problems

ii) Application of TM.

4.b. Construct a Turing Machine for R = (aba*b).

4.c. Construct Turing Machine that accepts string with equal number of 0's and 1's over = {0,1].

5.A. Prove that CFLs are closed under union, concatenation and Kleene's closure.

5.b. Design PDA for the following language -

5.c. Explain the working of Bottom-up parser with example.

6.a. Convert the following CGF to PDA -

S $\rightarrow$ aSb | A

a $\rightarrow$ bSa | s | $\epsilon$

6.b. Show that CFLs are not closed under intersection and complementation.

6.c. Explain acceptance by PDA -

i) By final state

ii) By empty state

7.a. Explain Tractable and Intractable problem.

7.b. How the Kruskal's Algorithm can be solve by using Turing Machine ?

7.c. Explain the Satisfiability Problem with an example.

8.a Prove that satisfiability Problem is NP - complete.

8.b. What do you mean by Polynomial Time reduction ? Explain with suitable example.

8.c. Differentiate between P and NP classes.