Department(s): Computer Science & Engineering

Year :II B.Tech

Semester: II Section(s):
FORMAL LANGUAGES AND AUTOMATA THEORY
Course duration:17-12-2015 to 20 -04- 2016

QUESTION BANK
UNIT 1: INTRODUCTION TO FINITE AUTOMATA

1. Define the following terms : (i) Alphabets (ii) Strings (iii) power of an alphabet (iv) language
2. Define DFA. Design a DFA to accept the binary numbers which are divisible by 5.
3. Obtain a DFA to accept strings of a’s and b’s starting with the string ab.
4. Give DFA’s accepting the following strings over the alphabet {0,1}
(a) The set of all strings containing 1101 as a substring.
(b) The set of all strings that begin with 01 and end with 11.

5. Obtain a DFA to accept strings of a’s and b’s except those containing the Substring aab.
6. Mention the differences between DFA,NFA and ε-NFA. Give the applications of Finite
Automata.
7. Draw a DFA to accept the Language :L=(w:w has odd number of 1’s and followed by even
number of 0’s.
8. Convert the following NFA to its equivalent DFA.

9. Obtain a DFA to accept strings of a’s and b’s having even number of a’s and b’s.

10. Obtain a DFA to accept strings of 0’s and 1’s having even number of 0’s and odd no. of 1’s.

11. Design DFA accepting the following languages over alphabet {a,b}
(a) L= {w:|w| mod 5 < > 0}(b) The set of all strings not containing ‘aab’

12. Prove that the DFA D constructed from NFA N by subset construction method
then L(D)=L(N) .

13. Obtain an NFA to accept strings of a’s and b’s ending with ab or ba and also write its
equivalent DFA.
14. Convert the following NFA N=({p,q,r,s},{0,1},ᵟ,{p},{r,s} to a DFA.
Where ᵟ is:
ᵟ(p,0)={p,r}, ᵟ(p,1)={q}, ᵟ(q,0)={r,s}, ᵟ(q,1)={p}, ᵟ(r,0)={p,s},
ᵟ(r,1)={r}, ᵟ(s,0)={q,r}, ᵟ(s,1)=Φ

15. Construct a NFA for the language

(i) L1={consisting a substring 0101}
 n n
(ii) L2={a Ub }
16. Consider the DFA with the following transition table. Informally describe the language
accepted by this DFA.
ᵟ 0 1
->A B A
B C A
*C C C
UNIT 2: FINITE AUTOMATA, REGULAR EXPRESSIONS

17. Define є-NFA and є-CLOSURE

18. Mention the differences between DFA,NFA and ε-NFA. Give the applications of
finite Automata.

19. Convert the following ε-NFA to DFA

20. Write DFA to accept strings of 0’s, 1’s & 2’s beginning with a 0 followed by odd number of
1’s and ending with a 2.
21. Consider the following ε-NFA. Convert the automata to a DFA. Give the set of all strings of
length 3 or less accepted by the automaton.
ᵟ ε a b
->P {r} {q} {p,r}
q Φ {p} Φ
*r {p,q} {r} {p}
n m n m
22. Write Regular expression for the following L = { a b : m, n are even} L = { a , b : m>=2,
n>=2}
23. Explain the extended transition function of є-NFA. Write the steps involved in the conversion
of є-NFA to DFA
24. Define regular expression and write regular expression for the following language:
2n 2m+1
L={a b : m≥0,n≥0}

25. Obtain an є-NFA to accept decimal numbers consisting of i) An optional + or – sign ii)
A string of digits iii)A decimal pt iv)another string of digits either this string of digits or
the string (2) can be empty ,but atleast one of the 2 string of digits must be non empty.
a) For the above є-NFA process the string 5.6 using extended transition function
Write the above є-NFA to DFA
26. Define regular expression. Obtain the RE for the following
i) To accept odd number 0’s and 1’s.
ii) To accept even number of a’s and b’s.
27. Define regular expression and write regular expression for the following language
L={The set of all strings over Ʃ = {a,b,c} contains at least one a & at least one b.}

28. Explain the equivalence relation between Finite automata and regular Expression.
29. Write the NFA which accepts L( r ) where r = ( a + bb)*(ba* + 

30. Prove that every language defined by a regular expression is also defined by FA.
31. Convert the regular expression (0+1)*10(0+1) to an ε-NFA.
32. Consider the DFA given below. Give all the regular expressions Rij(2).
 ᵟ 0 1

->A B A

B B C

*C C B

33. Convert the regular expression (10+1)*101(0+1)* to an ε-NFA.

UNIT 3: REGULAR LANGUAGES, PROPERTIES OF REGULAR LANGUAGES

34. Let M = (Q, ∑, ᵟ, q0, A) be an FA recognizing the language L. Then there exists an
equivalent regular expression R for the regular language L such that L = L(R).
35. If L1 and L2 are regular languages then prove that family of regular languages are closed
under L1-L2.

36. If L1 and L2 are regular languages then prove that family of regular languages are closed
under union.

37. Obtain a regular expression for the FA shown below:

38. State and prove pumping lemma for regular language.

39. What is the language accepted by the following FA

40. Write short note on Applications of Regular Expressions

41. Apply pumping lemma for the following language and prove that it is not
n
regular. L = {0 | n is a perfect square}
42. Apply pumping lemma to following languages and understand why we
cannot complete proof
n
A) L={a aba | n ≥0 }
n m
B) L={a b | n, m≥0 }
* *
43. Write a DFA to accept the intersection of L1=(a+b) a and L2=(a+b) b that is forL1 ∩ L2.
R
44. Prove that If L is a regular language, so is L
* * *
45. Find the DFA to accept the intersection of L1=(a+b) ab (a+b) andL2=(a+b) ba
(a+b)* that is for L1∩L2
46. Write down the closure properties of regular languages.
*
47. Prove that L={w|w is a palindrome on {a,b} } is not regular. i.e., L={aabaa, aba,abbbba,…}
48. Consider the DFA given by the transition table.
 ᵟ 0 1

->A B C
B C E
*C D C
D C E
*E B E
a) Draw the table of distinguishabilities for this automaton.
Construct the minimum state equivalent DFA.

UNIT 4: CONTEXT-FREE GRAMMARS AND LANGUAGES

49. Explain Context free grammar and context free languages.

50. Design context-free grammar for the following cases.

a) L={ 0n1n | n≥l }
b) L={aibjck| i≠j or j≠k}
51. The following grammar generates the language of RE
* *
0 1(0+1)
S A|B
A 0A|є
B 0B|1B|є
Give leftmost and rightmost derivations of the following strings
a) 00101 b) 1001 c) 00011

52. Define a Context-free grammar. Construct a CFG for the following languages
n R n i j k
(a) L={a ww b :w ϵ {a,b}* } (b) L={a b c |i=j+k , ∑={a,b,c}}
53. Define a Context-free grammar. Construct a CFG for the following languages
i j k
(a) L={w|w ϵ {0,1}* with at least one occurrence of '101'} (b)L={a b c |i+2j=k , ∑={a,b,c}}
54. Explain the following with suitable examples:

(i) Leftmost derivation (ii) Rightmost derivation (iii) Parse tree (iv) Yield of a parse tree
(v)Inherently ambiguous grammar
55. What is ambiguous grammar ? Show that the grammar shown below is ambiguous.
S-->AB |aaB A--> Aa|a B-->b

56. Consider the following grammar. Generate the LMD, RMD & Parse tree for the following
string .
W= badbabaadb
S--> AaAb | BbBa A-->aAb | bAB | d B-->aB |bBa |∈
57. Consider the grammar
S aS|aSbS|є
Show that deviation for the string aab is ambiguous
58. Define derivation tree, partial derivation tree, yield and Explain dependency graph & its
applications in CFG.
59. Let G = ( V,T,S,P) be a CFG. Then prove that for every w єL(G), there exists a derivation tree
of G whose yield is w.

UNIT 5: PUSHDOWN AUTOMATA

60. Define the instantaneous description of a NPDA & Give the formal definition of DPDA
61. What is an instantaneous description of PDA? Obtain a PDA to accept the following
n 2n
language by final state. L={a b | n>=1 ,∑={a,b}}. Draw the transition diagram for PDA
.Also
show the moves made by PDA for the string aabbbb.

62. What is PDA ? Explain with an example.

63. What does each of the following transitions represent?

a.  (p,a,Z)=((q,aZ)
b.  (p,a,Z)=(q,є)
c.  (p,a,Z)=(q,r)
d.  (p, є,Z)=(q,r)
e.  (p, є, є)=(q,Z)
f.  (p, є,Z)=(q, є)
64. Convert the following CFG to PDA that accepts same language by empty stack.
   
S aABB | aAA A aBB | a B bBB | A C a
65. Obtain a PDA to accept the Language L={w|w є(a,b)* and na(w) > nb(w)}

66. Obtain a PDA to accept the language L(M)={W|W є(a+b)* and na(W)=nb(W) i.e
the number of a’s in string w should be equal to number of b’s in w

67. Construct a NPDA for the following languages

a) L = { w є{ a,b}* : na(w) = nb(w)}
b) L = { wwr : w є{ a,b}+ }
68. Proof that if L is accepted by an empty stack PDA , then there exists an equivalent final state

PDA which accepts L.

71.
Convert the PDA P=({p,q},{0,1},{x, z0},δ,q,z0) to CFG. If is given by
 δ(q,1,Z0) = (q,xz0) δ(q,1,x)=(q,xx); δ(q,0,x)=(p,x)

δ(q, ,x)=(q, ); δ(p,1,x) = (p, ); δ(p,0,z0) = ( q,Z0)

72. Construct a NPDA that accepts the language generated by grammar with
productions
a) S aA
b) S Aabc|bB|a
c) B b
d) C c

UNIT 6: PROPERTIES OF CONTEXT-FREE LANGUAGES

73. State and prove Pumping Lemma for Context free language
74. Convert the following CFG into
CNF S ->bA|aB
A ->bAA| aS|a
B ->aBB|bS|b
75. Eliminate Left Recursion from the following grammar
E->E+T|T
T->T*F|F
F->(E)|id
76. Prove that CFL’s are closed under union,concatenation and star closure
77. Prove that family of CFL is not closed under intersection and complementation.
78. Show that the language L = { w є{ a,b,c}* : na(w) = nb(w) = nc(w) } is not context free.
n n n
79. Show that L={a b c |n>=0} is not Context free
80. What are the Applications of pumping Lemma?

UNIT 7: INTRODUCTION TO TURING MACHINE

81. Explain with diagram the operation of Turing machines? Give formal definition of
Turing machine.
n n n
82. Design a TM that accepts L = { a b c : n≥1 }
83. Define the operation of TM as transducers? Define a Turing computable function?
n n
84. Obtain a Turing machine to accept the language L={0 1 |n>=1}
n n n
85. Obtain a Turing machine to accept the language L(M)={0 1 2 |n>=1}
86. Obtain a TM to accept the language containing strings of 0’s and ‘s ending with 011
87. Design a Turing machine that halts at a final state if x≥y and at a non-final state if x<y
88. Design a TM that multiplies two +ve integers in unary notation
89. Prove that class of deterministic TM & class of non-deterministic TM are equivalent.
90. Define linear bounded automata(LBA)? When do we say that a string is accepted by a LBA?

UNIT 8: UNDECIDABILITY

91. Explain what is Undecidability & Define a recursively enumerable language & a recursive
language?
92. What are Recursive and Recursively Enumerable Languages.
92. Discuss the properties of Recursive & Recursively Enumerable Languages
93. Give convincing arguments that any language accepted by an off line Turing
machine is also accepted by some standard machine.
94. Discuss on Rice’s Theorem and Undecidable Problems.
95. Prove that Language Lu is not Recursive.
96. If PCP were decidable, then MPCP would be decidable that is MPCP reduces to PCP
97. Prove that for every recursively enumerable language L there exists an
unrestricted grammar G such that L = L(G).
98. Prove that The Union of two recursively enumerable Languages is recursively enumerable
99. Prove that The Complement of a Recursive Language is Recursive