FLAT 2 MARKS QUESTIONS
1. Define DFA ?
2. Mention the differences between DFA, NFA.
3. Construct the DFA that accepts all strings of a’s and b’s , no a’s are even or no.of b’s are even .
4. Construct the FA that accepts all strings of a’s and b’s, that every string starts with a and
length of the string not divisible by 3
5. Write down the decision properties of FA.
6. List the differences between Moore and Melay machines.
7. Obtain a DFA to accept strings of a’s and b’s starting with the string ab
8. List limitations of Finite Automata.
9. Define Moore machine.
10. Obtain a DFA to accept strings of a’s and b’s having even number of a’s and b’s
11. What is regular set and Regular Expression?
12. Simplify the RE (ab*+(ab)*)*a*
13. Construct the RE that generates all the strings of a’s and b’s i) including ε ii) excluding ε
14. Define CFG, LMD, RMD.
15. Find a RE for the set of all strings containing no three consecutive 0’.
16. What is the difference between Regular and context free grammar?
17. Construct a regular grammar for the regular expression a*b(a+b)*
18. List closure properties of regular languages.
19. Prove for the RE a and b i. (ab+a)*a=a(ba+a)* ii (a*b*)*=(a+b)*
20. Find the left most derivation for the word abba in the grammar S->AA, A->aB, B->bB/ε.
21. Prove the grammar is ambiguous. Sa|Sa|bSS|SSb|SbS
22. Convert the following grammar to Greibach normal form S-> ABA|AB|BA|AA|B, A->aA|a ,
B->bB|b
23. Construct the PDA for the following grammar S->AA|a A->SA|b What is DPDA? What are the
difference between PDA and DPDA?
24. For the CFG remove the ε production S->aSa/ bSb/ε
25. Explain Chomsky’s normal form with example.
26. Explain Greibach normal form with example.
27. When a CFG is said to be GNF?
28. List out the properties of CFG?
29. Define Turing Machine?
30. What is Type 1 grammar?
31. Design TM for L={0n1n0n|n>=1}
32. Define Recursively enumerable language?
33. Construct TM to add two given integer?
34. What are the types of TM?
35. What are the properties of Recursive and recursively Enumerable language?
36. Define Churchs’ s Hypothesis?
37. What are the limitations of TM?
38. Make a comparison between FM,PDA and TM?
39. What is Decidability? Explain with example?
40. Explain Universal TM?
41. What is COUNTER Machine?
42. What is P,NP, NP-complete and NP-hard?
43. Explain Chomsky Hierarchy in details?
44. What is PCP ? Or Universal TM ?
45. explain Homomorphism ii) Recursive language
46. What is Turing Machine and Multi tape Turing Machine? Show that the languages accepted by
these machines are same.
47. What is decidability of a problem explain in details?
48. Design Turing Machine for the language
