a b
L
k k
∈ but a b
L
m k
∉ . Hence there are infinitely many ≡ L -classes, at least
one for each a k
k ,
.
≥ 0
Hence by Myhill-Nerode Theorem L is not regular. (The application of
Myhill-Nerode theorem has been illustrated above).
GLOSSARY
Automaton: Abstract model of a digital computer.
Acceptor: Automaton whose output response is “Yes” or “No”
DFA: Deterministic Finite Automata.
NFA: Non-deterministic Finite Automata.
Regular Language: Language that can be constructed from the set
operations—Union, Concatenation and Kleene star.
Regular expression: Mathematical tool built from a set of primitives and
operations.
Two-way Finite Automata: Machines that can read input string in either
direction.
Moore machine: Output function depends only on present state and
independent of present input.
Mealey machine: Value of the output function is a function of the present
state and present input in a Mealey Machine.
Pumping lemma: A way to show that an infinite language is not regular.
REVIEW QUESTIONS
1. Define the term ‘Automata’ with an example.
2. What are the types of Automaton?
3. Explain Deterministic automata with an example.
4. Explain Non-deterministic automaton with an example.
5. Distinguish between DFA and NFA.
6. Explain the terms:
(a) State Table diagram
(b) State Transition diagram.
7. Define Non-deterministic Finite automata.
8. Comment on the equivalence of NFA and DFA.
9. What are regular expressions?
10. Define a regular language.
11. Give examples for regular expressions.
DFA and NFA
99