1. Define Following. [1 – 2 Marks]

- Principle of Weak Induction
- Deterministic Finite Automata (DFA)
- Non- Deterministic Finite Automata (NFA)
- NFA – Λ
- Λ – Closure of a Set of States for NFA-Λ
- Context Free Grammar (CFG)
- Pushdown Automata (PDA)
- Turing Machine
- Linear Bounded Automata (LBA)
- Pumping Lemma for Regular Language
- Pumping Lemma for Context Free Language

2. Differentiate followings. [2 – 3 Marks]

- DFA Vs. NFA Vs. NFA – Λ
- Direct Proof Vs. Indirect Proof
- Σ* Vs. Σ+
- Accept by Empty Stack Vs. Accept by Final State

3. Answer the following. [6 – 7 Marks]

- Explain Chomsky Hierarchy in detail.
- Discuss Turing Machine and explain Configuration of TM.
- What do you mean by Ambiguity? Discuss Derivation Tree and Ambiguity in context of CFG.
- Prove that “Any language accepted by any Finite Automaton is regular”.
- Which machine is used to recognize CFL? Explain it with its data structure.

Explain the different way by which it accepts Language.

4. Prove that for every n>0

5. Suppose a and b are integers with 0 ≤ a ≤ b. Prove that for every n≥1,

b

^{n}– a^{n }is divisible by b-a.6. Draw DFA for following

- All string over {0, 1} that ends with substring 001.
- All string over {0, 1} that contains substring 0110.
- All string over {0, 1} that starts with substring 011.
- Given that L1 = {x є (0,1)* | x ends with 11}, L2 = {x є (0,1)* | x ends with 10}

Give FA for L1, L2 and L1 U L2

e. For Regular Expression (a + b)* abb.

7. Calculate the Following. δ*(1,aabbab) (ii) δ*(1,bab) for following NFA.

8. A Transition table is given for an NFA- Λ with Seven States.

q | δ(q, a) | δ(q, b) | δ(q, Λ) |

1 | ø | ø | { 2 } |

2 | { 3 } | ø | { 5 } |

3 | ø | { 4 } | ø |

4 | { 4 } | ø | { 1 } |

5 | ø | { 6, 7 } | ø |

6 | { 5 } | ø | ø |

7 | ø | ø | { 1 } |

Find: (i) Λ ({3,4}) (ii) δ*(1, ab)

9. Using Algorithm Draw an NFA accepting the same Language.

10. Using Subset Construction Draw FA for Given.

11. The Length of a function can be defined as follow.

(i) | Λ |=0

(ii) For any x є Σ* and any a є Σ, |x a| = |x| + 1

Prove that for every x and y in Σ*, |x y| = |x| + |y|

12. Convert aa (ba)* + b*aba* to an NFA-Λ.

13. For the following FA, Use the minimization algorithm to find a Minimum State FA recognizing the same Language.14. Prove that Following Languages are Not Regular.

- Pal the Language of Palindrome over {0, 1}
- L = { 0
^{n }| n is Prime } - L = { 0
^{i }1^{j}| i > j }

15. Find out CFG for L = { x є {0, 1}* | n

_{0}(x) = n_{1}(x) }16. Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.

S → A | B. A → aAb | ab. B → abB | Λ

17. Convert following CFG in to CNF.

S → AACD.

A → aAb | Λ

C → aC | a

D → aDa | bDb | Λ

18. Find out CFG for

- L = { a
^{i }b^{j }c^{k}| j=i or j=k } - L = { a
^{i }b^{j }| i < 2j }

19. Construct DPDA for Language L = { x є {a, b}* | n

_{a}(x) > n_{b}(x) } Show the Sequence of Moves for Input String : bbabaa

20. Give Transition table and Transition Diagram for the Language of Palindrome.

Draw Computation Tree for Input String aba.

21. Construct TM Accepting Language pal of Palindrome.

Show the Sequence of Moves for Input String (1) ab (2) bab

23. Construct TM to compute n mod 2. Show the Sequence of Moves for (1) n=2 (2) n=3

24. Prove that L = { x є {a, b, c}* | n

_{a}(x) < n_{b}(x) and n_{a}(x) < n_{c}(x) } is not Context Free Language.

25. The language L {0,1}* is defined as follows:

1. 0 є L

2. For any x є L, 0x є L

3. For any x and y in L, all the strings 1xy, x1y, and xy1 are in L

4. No other strings are in L.

Prove that every element of L has more 0’s than 1’s Using Structural Induction.