Information Technology Reference
In-Depth Information
≡
j
and forms equivalence
algorithm compares each pair of states in an equivalence class of
≡
j
+
1
by grouping together states whose successors under input letters are in the
same equivalence class of
classes of
≡
j
.
To illustrate these ideas, consider the DFSM of Fig.
4.14
. The equivalence classes of
≡
0
are
{{
s
0
,
q
R
}
{
q
1
,
q
2
,
q
3
}}
.Since
δ
(
s
0
,0
)
and
δ
(
q
R
,0
)
are different,
s
0
and
q
R
are in different
,
≡
1
. Also, because
δ
(
q
3
,0
)=
q
R
and
δ
(
q
1
,0
)=
δ
(
q
2
,0
)=
q
1
∈
F
,
q
3
is
equivalence classes of
≡
1
from
q
1
and
q
2
. The latter two states are in the same equiv-
alence class because
δ
(
q
1
,1
)=
δ
(
q
2
,1
)=
q
R
∈
in a different equivalence class of
F
.Thus,
≡
1
=
{{
s
0
}
{
q
R
}
{
q
3
}
{
q
1
,
q
2
}}
.
The only one of these equivalence classes that could be refined is the last one. However, since
we cannot distinguish between the two states in this class under any input, no further refine-
ment is possible and
,
,
,
≡
1
.
We now show that if two states are equivalent under
≡
=
≡
, they can be combined, but if they
≡
are distinguishable under
, they cannot. Applying this procedure provides a minimal-state
DFSM.
DEFINITION
4.7.8
Let
M
=(Σ
,
Q
,
δ
,
s
,
F
)
be a DFSM and let
≡
be the equivalence relation
defined above over
Q
.TheDFSM
M
≡
=(Σ
,
Q
≡
,
δ
≡
,
[
s
]
,
F
≡
)
associated with the relation
≡
is defined as follows: a) the states
Q
≡
are the equivalence classes of
; b) the initial state of
M
≡
is
[
s
]
; c) the final states
F
≡
are the equivalence classes containing states in F; d) for an arbitrary
equivalence class
[
q
]
with representative element
q
≡
∈
Q
and an arbitrary input letter
a
∈
Σ
,the
next-state function
δ
≡
:
Q
≡
×
Σ
→
Q
≡
is defined by
δ
≡
([
q
]
,
a
)=[
δ
(
q
,
a
)]
.
This definition is consistent; no matter which representative of the equivalence class
[
q
]
is
used, the next state on input
a
is
[
δ
(
q
,
a
)]
. It is straightforward to show that
M
≡
recognizes
the same language as does
M
. (See Problem
4.27
.)Wenowshowthat
M
≡
is a minimal-state
machine.
THEOREM
4.7.2
M
≡
is a minimal-state machine.
Proof
Let
M
=(Σ
,
Q
,
δ
,
s
,
F
)
be a DFSM recognizing
L
and let
M
≡
be the DFSM
≡
on
Q
. Without loss of generality, we assume
associated with the equivalence relation
that all states of
M
≡
are accessible from the initial state. We now show that
M
≡
has no
more states than
M
L
. Suppose it has more states. That is, suppose
M
≡
has more states
than there are equivalence classes of
R
L
. Then,theremustbetwostates
p
and
q
of
M
such that
[
p
]
=[
q
]
but that
u
R
L
v
,where
u
and
v
carry
M
from its initial state to
p
and
q
, respectively. (If this were not the case, any strings equivalent under
R
L
would carry
M
from its initial state
s
to equivalent states, contradicting the assumption that
M
≡
has more
states than
M
L
.) But if
u
R
L
v
,thensince
R
L
is right-invariant,
uw
R
L
vw
for all
w
Σ
∗
.
∈
Σ
∗
such that
[
p
]
and
[
q
]
can be distinguished.
This is equivalent to saying that
uz
R
L
vz
does not hold, a contradiction. Thus,
M
≡
and
M
L
have the same number of states. Since
M
≡
recognizes
L
, it is a minimal-state machine
equivalent to
M
.
However, because
[
p
]
=[
q
]
, there is some
z
∈
As shown above, the equivalence relation
≡
for the DFSM of Fig.
4.14
is
≡
is
{{
s
0
}
,
{
. The DFSM associated with this relation,
M
≡
,isshowninFig.
4.21
.
It clearly recognizes the language 10
∗
+
0. It follows that the equivalent DFSM of Fig.
4.14
is
not minimal.
q
R
}
,
{
q
3
}
,
{
q
1
,
q
2
}}
Search WWH ::
Custom Search