Information Technology Reference
In-Depth Information
4.7.2 The Myhill-Nerode Theorem
The following theorem uses the notion of refinement to give conditions under which a lan-
guage is regular.
THEOREM
4.7.1
(Myhill-Nerode)
L
is a regular language if and only if
R
L
has a finite num-
ber of equivalence classes. Furthermore, if
L
is regular, it is the union of some of the equivalence
classes of
R
L
.
Proof
We beg in by showing tha t i f
L
is regular,
R
L
has a finite number of equivalence
classes. Let
L
be recognized by the DFSM
M
=(Σ
,
Q
,
δ
,
s
,
F
)
. Then the number of
equivalence classes of
R
M
is finite. Consider two strings
u
,
v
Σ
∗
that are equivalent
under
R
M
.Bydefinition,
u
and
v
carry
M
from its initial state to the same state, whether
final or not. Thus,
uz
and
vz
also carry
M
to the same state. It follows that
R
M
is right-
invariant. Because
u
R
M
v
,either
u
and
v
take
M
to a final state and are in
L
or they take
M
to a non-final state and are not in
L
. It follows from the definition of
R
L
that
u
R
L
v
.
Thus,
R
M
is a refinement of
R
L
.Consequently,
R
L
has no more equivalence classes than
does
R
M
and this number is finite.
Now let
R
L
have a finite number of equivalence classes. We show that the machine
M
L
recognizes
L
. Since it has a finite number of states, we are done. The proof that
M
L
recognizes
L
is straightforward. If
[
w
]
is a final state, it is reached by applying to
M
L
in
its initial state a string in
[
w
]
. Since the final states are the equivalence classes containing
exactly those strings that are in
L
,
M
L
recognizes
L
. It follows that if
L
is regular, it is the
union of some of the equivalence classes of
R
L
.
∈
We now state an important corollary of this theorem that identifies a minimal machine
recognizing a regular language
L
.TwoDFSMsare
isomorphic
if they differ only in the names
given to states.
COROLLARY
4.7.1
If
L
is regular, the machine
M
L
is a minimal DFSM recognizing
L
.Allother
such minimal machines are isomorphic to
M
L
.
Proof
From the proof of Theorem
4.7.1
,if
M
is any DFSM recognizing
L
,ithasnofewer
states than there are equivalence classes of
R
L
, which is the number of states of
M
L
.Thus,
M
L
has a minimal number of states.
Consider another minimal machine
M
0
=(Σ
,
Q
0
,
δ
0
,
s
0
,
F
0
)
. Each state of
M
0
can
be identified with some state of
M
L
. Equate the initial states of
M
L
and
M
0
and let
q
be
an arbitrary state of
M
0
. There is some string
u
Σ
∗
such that
q
=
δ
0
(
s
0
,
u
)
.(Ifnot,
M
0
is not minimal.) Equate state
q
with state
δ
L
(
s
L
,
u
)=[
u
]
of
M
L
.Let
v
∈
∈
[
u
]
.
If
δ
0
(
s
0
,
v
)
=
q
,
M
0
has more states than does
M
L
, which is a contradiction. Thus, the
identification of states in these two machines is consistent. The final states
F
0
of
M
0
are
identified with those equivalence classes of
M
L
that contain strings in
L
.
Consider now the next-state function
δ
0
of
M
0
.Letstate
q
of
M
0
be identified with
state
[
u
]
of
M
L
and let
a
be an input letter. Then, if
δ
0
(
q
,
a
)=
p
, it follows that
p
is
associated with state
[
u
a
]
of
M
L
because the input string
ua
maps
s
0
to state
p
in
M
0
and
maps
s
L
to
[
u
a
]
in
M
L
. Thus, the next-state functions of the two machines are identical
up to a renaming of the states of the two machines.
Search WWH ::
Custom Search