1.a. Design Moore machine for divisibility by 3 tester for binary number.

1.b. Discuss Applications of FA & regular expressions.

2.a. Using Pumping lemma, Prove that L = is not- regular

2.b. Design Finite Automata to accept strings ending with 00 or 11.

3.a. Simplify the following Grammar

S→a | Xb | aYa

X → Y|∈

Y → b|X

3.b. Write an equivalent left-linear grammar for the right-linear grammar, which is defined as :

S → 0A | 1B

A → 0C|1A|0

B → 0|0A

4.a. Check whether or not the following grammar is ambiguous; if it is ambiguous, remove the ambiguity and write an equivalent unambiguous grammar.

S → aS | aSbS | ∈

4.b. Write Short Note on Chomsky Hierarchy.

5.a. Construct PDA that accepts language.

L = {aⁿ bᵐ cⁿ | m, n ≥ 1}

5.b. Construct PDA to check for well formedness of paranthesis. Write ID for

i. (() ())

ii. (())

6.a. Construct Post Machine which accepts the string over Σ = {a, b} containing odd length & the element at the centre as 'a'.

Writ simulation for string abbabba

6.b. Convert the following CFG into CNF & construct PDA for the same.

S → 0A1 | 0BA

A→S01|0

B → 1B|N

7.a. Design a TM that multiplies two unary numbers.

Write simulation for the strings.

11 & 111

7.b. Compare FA and TM.

7.c. Define Recursive languages & Recursively enumerable languages with example

8.a. Design TM to find 2's compliment.

8.b. Construct a TM to compute

f (a, b) = a − b where a > b

= 0 where a ≤ b

8.c. Explain Multitape TM

9.a. Prove that, following are decidable languages

i. = {⟨G,w⟩| Where G is a CFG that generates string w}

ii. - {⟨G, w⟩| where G is a CFG and L(G) = }

9.b. Write short note on NP completeness with examples.

10.a. Prove that,

= {⟨M, w⟩| M is TM & M halts on input w} is undecidable.

10.b. Write short notes on

i. PCP

ii. Measuring Complexity