FORMAL LANGUAGE AUTOMATA THEORY

1. Write the steps for construction of minimization of automaton?
2.  Show that L = { WW / W є { a ,b}*} is not regular?
3. Construct   FA  which can accept strings over an alphabet a,b…….containing       either cat  or rat?
4. Show that there exist no FA accepts all palindromes over { a , b }?
5. Define DFA & NFA with example?
6. Construct FA the set of all strings containing substring 101?
7. Write the steps to convert NFA to DFA?
8. Explain about FA with output?
9. Construct FA the set of all strings contains even no of 0’s & 1’s over {0,1}?
10. Construct NFA for (11+0)*(00+1)*?
11.  Construct DFA for ternary number is divisible by 5?
12.  Construct FA from the given grammar

       S -> aS / bS / aA

             A -> bB

       B -> aC

             C -> A

13. Design a DFA for the following language L={0ª1^b / a>=0 & b>=1}?
14. Design a Moore machine to determine the residue mod 4 for each binary string treated as integer
15. Design a mealy machine that uses its state to remember the last symbol read and emits output y whenever current input matches to previous one, and emits n otherwise?
16. For the following NFA with є moves to without є moves?