Myhill-Nerode theorem
Let be a language on the finite alphabet
and let be its Nerode equivalence.
The following are equivalent
.
-
1.
is recognized by a deterministic finite automaton.
-
2.
is finite.
Moreover, the number of classes of is the smallest number of states of a DFA recognizing .
Proof.
First, suppose
where is the empty word on .
Construct a DFA
(called the Nerode automaton for )
with defined by
(1) |
and
(2) |
Then is well defined because implies . It is also straightforward that recognizes .
On the other hand, let be a DFA that recognizes . Extend to by putting and for every , , . Define as
(3) |
Then is well defined.
In fact, suppose :
then either ,
or there are such that .
But in the latter case,
for any ,
hence since recognizes .
Finally, for any we have
so every class of has a preimage according to ;
consequently, .
Title | Myhill-Nerode theorem |
---|---|
Canonical name | MyhillNerodeTheorem |
Date of creation | 2013-03-22 18:52:13 |
Last modified on | 2013-03-22 18:52:13 |
Owner | Ziosilvio (18733) |
Last modified by | Ziosilvio (18733) |
Numerical id | 14 |
Author | Ziosilvio (18733) |
Entry type | Theorem |
Classification | msc 68Q70 |
Classification | msc 20M35 |
Synonym | Myhill-Nerode theorem for languages |