IMPORTANT QUESTIONS
23AD1501 – FORMAL LANGUAGE AND AUTOMATA THEORY
PART - A
1. Let M = (Q, Σ, δ, q0, F) where Q= {q0, q1, q2}, Σ= {a, b} F= {q2}
δ a b
q0 q1 q0
q1 q1 q2
*q2 q2 q2
Show that the string w = “bbabb” is accepted by the given FA.
2. Lists the Closure properties on Regular set.
3. Distinguish between D F A and NFA
4. Give the English description of the language (b*(aaa)*b*)
5. Construct the finite automata for regular expression ab
6. Write the regular expression for the set of all strings with even number of a’s and odd number of b’s.
7. State Arden’s theorem.
8. State pumping Lemma and List out the applications of pumping Lemma.
*
9. Construct NFA for the following expression with ℇ transition (ab)
10. Give two strings that are accepted and two strings rejected by the following finite automata M= ({q0, q1,
q2, q3, q4}, {0,1}, δ, q0, {q2}).
11. Find ε-closure for the following non-deterministic finite automata (NFA) with epsilon.
12. Write a regular expression for the language which accepts all strings with atleast two a’s over
the set Σ= {a, b}.
13. Find regular expression for the following DFA.
14. Convert the following regular expressions to NFAs with ε- transitions abb(a+b)*.
15. Prove that the complement of a regular language is also regular.
16. List out the properties of kleen closure
17. State Pumping Lemma for regular Languages.
18. Derive the string "00101" for rightmost derivation using a CFG given by,
S → A1B
A → 0A | ε
B → 0B |1B | ε.
19. Define ambiguous grammar and CFG.
20. Removal of Unit Productions- Discuss
PART – B
1. Construct the DFA equivalence to the NFA given by M=({q0, q1}, {0,1}, δ, q0, {q2}) where
δ(q0,0) = {q0,q1}, δ(q0, 1)=q1, δ(q1,0)= ϕ, δ(q1,1)= {q0, q1}
2. Construct ε-NFA for the following expression (01+0*)01* and Convert the ε-NFA to DFA and
list the difference between NFA and DFA
3. Covert the given automata into minimized DFA
4. Myhill Nerode theorm – Discuss the steps with a neat sketch
5. Minimize the following automaton
6. Explain in detail the properties of kleene closure
7. Prove that the following language are not regular using pumping
Lemma.
n n
i. L= {a b |n ≥1}
p
ii. L= {a | p is a prime}
8. Illustrate the formation of a derivation tree, by examining the derivation of the string "001"
from the grammar G
9. Given the grammar G= (V, Σ, P, S) with the following production rules (P)
S → AC | B,
A → a,
C → c | BC,
E → aA | e
Find a reduced grammar equivalent to G
10. Explain in detail about alphabets and string properties, components with an example
11. Consider the following ε-NFA. Compute ε – closure of each state and find its equivalent DFA.
12. Given ∑= {a, b} construct a DFA which recognize the language
i. L= {bm an | m, n>0}.
ii. Construct the DFA accepting the language over the alphabet ∑= {0,1}, where number of
1’s is a multiple of 3.
13. Convert the following NFA to a DFA and informally describe the language it accepts.
δ 0 1
→p {p, q} {p}
q {r, s} {t}
r {p, r} {t}
*s ϕ ϕ
*t ϕ ϕ
14. [Link] a FA for the RE (0 +1)* (00 + 11)01.
n n
[Link] that the language L = { a b |n ≥0} is not regular
15. Find the regular expression for the following DFA.
16. Write and explain algorithm for minimization of a DFA. Minimize the following automaton.
17. i. Solve the following grammar:
S→aAa | bBb | BB
A→C
B→S|A
C→S | є
For the string “abaabbba”. Find left most, rightmost derivation and parse
tree. [Link] that the following grammar is ambiguous:
{S → a | S + S | S S | S*S | ( S ) }.
n n n
18. i. Find out whether L= {x y z | n>=1} is context free or not. [Link] L be the
R
language {ww | w ∈ {0, 1} *. Show that this language is not a CFL.
PART – C
1. Construct a regular expression denoting the set of all strings over {a, b}
such that all starts with ‘a’ and ends with “ab” construct DFA for the same.
2. Construct the minimized DFA for the following automata and write the regular
expression for minimized DFA.
3. Construct a minimal DFA for the language L over input alphabets ∑ = {0, 1} for the
regular expression (0+1)*100
4. Construct the minimized DFA for the given automata.