Next: Formalizing
Up: The Myhill-Nerode Theorem
Previous: The Myhill-Nerode Theorem
Theorem 3.1. The following three statements are
equivalent:
- The set
is accepted
by some finite automaton.
-
is the (effective) union of some of the equivalence classes of an extension invariant equivalence relation of finite index.
- The equivalence relation on
induced by is of finite index (and decidable).
Proof
. Assume that is accepted by
. Let 
be the
equivalence relation 
if and only if 
. is extension invariant since, for any 
, if
then
The index of is finite since the index is at most the number of
states in 
. Furthermore, is the union of those equivalence
classes which include an element 
such that 
is
in 
.
.
We show that any equivalence relation satisfying 
is a
refinement of 
; that is, every equivalence class of is
entirely contained in some equivalence class of . Thus the index
of cannot be greater than the index of and so is finite.
Assume that . Then since is extension invariant, for each
in , 
, and thus 
is in if and
only if 
is in . Thus 
, and hence, the equivalence
class of in is contained in the equivalence class of in
. We conclude that each equivalence class of is contained
within some equivalence class of .
Assume that . Then for each 
and in , 
is in if and only if 
is in . Thus 
, and is extension invariant. Now let 
be the finite set
of equivalence classes of and 
the element of
containing . Define 
. The definition is
consistent, since is extension invariant. Let 
and let 
. The finite
automaton 
accepts since
, and thus is in 
if and only if
is in 
. Note, is computable because we assume is
decidable.
Qed
Theorem 3.2. The minimum state automaton accepting is
unique up to an isomorphism (i.e., a renaming of the states) and is
given by 
of Theorem 3.1.
Proof
In the proof of Theorem 3.1 we saw that any 
accepting defines an equivalence
relation which is a refinement of . Thus the number of states of
is greater than or equal to the number of states of of
Theorem 3.1. If equality holds, then each of the states of can be
identified with one of the states of . That is, let 
be a
state of . There must be some in , such that 
, otherwise could be removed from , and a
smaller automaton found. Identify with the state 
of . This identification will will be consistent.
If 
, then, by Theorem
3.1, and 
are in the same equivalence class of . Thus
.
Qed
Note, some authors [22] use the term Myhill/Nerode relation for to refer to an extension invariant equivalence relation of finite index which refines . Using this terminology, statement (2) becomes
2. There is a Myhill/Nerode relation for .
Next: Formalizing
Up: The Myhill-Nerode Theorem
Previous: The Myhill-Nerode Theorem