12. Comment on the correspondence between regular expressions and the
languages they denote.
13. How will you convert an NFA to a regular expression?
14. What do you mean by two way finite automata?
15. What do you mean by finite automata with output.
16. What do you mean by a Mealy machine?
17. What do you mean by a Moore machine?
18. Give examples for Moore and mealy models of finite automata with
outputs.
19. State the properties of regular sets.
20. State the principle of pumping lemma.
21. Define Pumping lemma.
22. Explain the closure properties of Regular languages.
23. What is Isomorphism?
24. State the Myhill-Nerode relations.
EXERCISES
1. For Σ = { , }
a b construct DFA that accepts the following set of strings
(a) all strings with exactly one ‘a’
(b) all strings with at least one ‘a’
(c) all strings with no more than three a’s
(d) all strings with at least one ‘a’ and exactly two b’s.
(e) L = { w : | w | mod 3 = 0 }
(f) L = { w : | w | mod 5 ≠ 0 }
2. Determine a DFA that accepts all strings on {0,1} except those
containing the substring 001.
3. Obtain the NFA for a language defined by
L a b n m
n m
=
≥
{
,
}.
1
and its associated state table diagram.
4. Construct an NFA for the state table given below.
δ
0
1
q 0
{q 0 , q 1 }
{q 3 }
q 1
{q 0 }
{q 1 , q 3 }
q 2
∅
{q 0 , q 2 }
q 3
{q 1 , q 2 , q 3 }
{q 1 }
100
Theory of Automata, Formal Languages and Computation