Question Bank
Formal Language and Automata
(UCSL203)
1. Define Chomsky Normal form for context free grammar. Reduce the following
grammar to Chomsky Normal form.
G= ({s}, {a, b, c}, {s→ a/b/css },s)
2. Explain Chomsky classification of languages.
3. Let L be the set of all palindromes over{a,b} .Construct a grammar generating L.
4. Define context free grammar and find the context free grammar for the
following languages:
i) L= {anbm: n≤m+3} ii) L={anbm : n≠2m}
5. Find the grammar in CNF equivalent to the grammar.
S→~S |[S ⊃ S] | p | q (S being the only variable).
6. If G=({s},{a},{S→SS},S).Find the language generated by G.
7. The production of any grammar ε is given by
S→0B/1A
A→0/0S/1AA
B→1/1S/0BB
Find the string 00110101; find the leftmost derivation, right most derivation and
derivation tree.
8. Consider the following productions
SaB|bAA|a, BbS|aBB|b for the string aaabbabbba.Find
theLeftmost Derivation ii) Right Most Derivation and iii) Parse
Tree.
9. Show that grammar SaB/ab, A aAB/a, B ABb/b is ambiguous.
10. Convert the PDA to CFG.
A= ({q0, q1}, {a, b}, {z0, z}, δ, q0, z0,Ø)
δ is given by
δ (q0,b,z0)= (q0,zz0)
δ (q0,n,z0)= (q0,n)
δ (qo,b,z)= (q0,zz)
δ (q0,a,z)= (q1,z)
δ (q0,b,z)= (q1,n)
δ (q1,a,z0)= (q0,z0)
11. Design PDA which accept the following Language
L={anbn | n>=1}
L={WcWr | W is set of strings of a’s,b’s}
12. Design a Turing machine M to recognize the language {1n2n3n, n>1}.
13. Write short notes on :
i) Universal Turing machine
ii) Halting problem
iii) Multitape and multi dimensional Turing machine.
iv) Define a) Solvability b)Semisolvability c)Unsolvability
14. Design the TM which recognizes following languages :
a) Design Turing machine M that recognize the language {anbncn/n>1}
b) Design Turing machine M that recognize the language {anbn/n>=1}
c) Design Tm which will compute 2‟s complement of a no. Also give processing
of “00000”by the TM.
d) Design a TM to recognize WW where w is string of a‟s and b,s.
15. Explain Turing machine with its various way of representation. Draw diagram whenever
required.
16. Write short notes on the following:
i) Recursive and Recursively Enumerable languages.
ii) Context free grammar and context sensitive grammar
17. Which of the following are context sensitive
grammar? GivenVN= {S, A, B, D}
S= {0,1,a,bc}, where A is start symbol
a) A→BB
b) A→0B
c) SA→S0A
d) SAB→S0A1
e) aABbcD→abcDbcd
f) 01→10
g) aBAbCD→abcDbcD
18. Explain the following:
i) Subroutines
ii) Closure properties of recursive and recursively enumerable language.
19. For the following NDFA find equivalent DFA.
State Inputs
0 1
→q0 {q0, q1} {q0, q3}
q1 {q2} Ø
q2 Ø Ø
q3 Ø {q4}
q4 Ø Ø
20. Consider DFA m=({q0,q1,q2},{a,b},s,q0,{q1,q2}) such that δ(q0,a)=q2, δ(q1,b), δ(q0,a)=q0,
δ(q1,b)=q1, δ(q2,a)=q2, δ(q2,b)=q0,find out regular expression for the language accepted by
M. also express the language
21. Construct a deterministic finite automata equivalent to the following NDFA.
22. What is automata? Explain finite automata with neat and labeled diagram. Also
check acceptability of string 101101 for the given automata. .
23. Find deterministic (DFA) for the following non-deterministic finite automaton.
24. Conversion of NDFA to DFA
25. Design a DFA containing all strings with
i) Exactly one a;
ii) At least one a Take ∑={a,b}
26. Construct a transition system which accepts set of string over ∑= {0,1} and is with
even no. of zeros and even no. of ones. Also find the acceptability of the string 110101.
27. Define finite automata. Differentiate between following terms and their purpose .
i) Final states, trap states, non final states
ii) Deterministic and non deterministic finite acceptors.
28. Suppose we restrict DFA so that they have at most one accepting state. Can any
regular language L be recognized by this restricted from of DFA? Justify your answer?
29. Define regular expressions and languages associated with regular expressions. Write the
regular expression and finite automata (transition diagram) for following languages over
alphabets ∑= {a,b}.
i) The set of strings that start with “ab” end with “bb”.
ii) The set of strings that starts with “a” and ends with “b” and contain at least
one sequence of “aaa” in that strings.
30. Write regular expressions for each of the following language over alphabet {a,b }.
i) The set of strings containing „ab‟ as a substring.
ii) The set of string having at most one pair of consecutive a‟s and at most one pair
of consecutive b‟s.
iii) The set of strings whose length is divisible by 6.
iv) The set of strings whose 5th last symbol is b.
31. Construct a finite automata equivalent to the regular expression.
. (0+1)*(00+11)(0+1)*
32. Construct an NFA that accepts the set of strings defined over ∑={0,1} that starts with
1 and accepts the string of |w| mod 3=0
L={x ∈ ∑ * : x starts with 1 and |x| mod 3=0} Convert the NFA into equivalent DFA.
33. State and explain pumping lemma. Prove that following expression is not regular
using pumping Lemma; L= {anbn: n≥1}
34. Write the closure properties of regular languages. Explain pigeon hole principle.
Prove that language L= {anbn: n≥0} is not regular using method of contradiction.
35. Show that the following language L= {an: n is a perfect square} is not regular.
36. Consider a Mealy machine given by transition diagram. Construct a Moore machine
equivalent to this Mealy machine. .
37. Construct a Moore machine equivalent to the mealy machine M defined by the table
given below: .
Present Next state
state
a=0 b=1
state output stat output
e
q1 q1 1 q2 0
q2 q4 1 q4 1
q3 q2 1 q3 1
q4 q3 0 q1 1
38. Construct a mealy machine with ∑=∆= {0,1}. The output is 1 whenever the last four
symbols read are 1111. Overlapping sequence are accepted. Output is 0 otherwise.
39. Consider a Mealy machine given by transition diagram. Construct a Moore
machine equivalent to this Mealy machine.
40 Design DFA for the Language of (a,b) containing “aba” as substring and not containing
“bab” assubstring
41 Construct DFA equivalent to NFA M = ({p,q,r,s}, {0,1}, δ, p, {s}) where δ is,
δ 0 1
p p,q p
q r r
r s -
s s s
42. Construct a Moore Machine equivalent to Mealey Machine
Present Next State
State a=0 a=1
State O/P State O/P
→ q1 q1 1 q2 0
q2 q4 1 q4 1
q3 q2 1 q3 1
q4 q3 0 q1 1
43. Define: NFA with Є-moves and explain Є-closure of a state.
44. Design the Minimum State DFA From the following Regular
Expression.(ab)*.bab*+ab*(bb)*
45. Convertthe following Right Linear Grammar to Left Linear
Grammar
S abS/aA
A aaA/ba
46. Reduce the following
Grammar
S aA/aBB
A aaA/€
A bB/bbC
47. Convert the following into
CNF
48. S SaSa/bBb
B abB/aaAa
A Aa/a
49. Define Ambigiuios Grammar & un ambigious grammar with
example
50. Explain Pumping Lemma for regular sets.
Show that L= {0i1i/i≥1} is not Regular
50 Explain the Model of Push down Automata
51. Design a PDA for the Following Language L = {an bm cm-n /m,n≥0}
