Information Technology Reference
In-Depth Information
1
1
b
c
0
0
Start
0
0
a
d
1
q
R
1
0, 1
Figure 4.3
The DFSM
M
equiv
equivalent to the NFSM
ND
.
We first give an inductive definition of the states of
M
2
.Let
Q
(
k
2
denote the sets of states
of
M
1
that can be reached from
s
1
on input strings containing
k
or fewer letters. In the
example given above,
Q
(
1
)
2
and
Q
(
3
)
2
=
{{
q
0
}
,
{
q
1
,
q
2
}
,
q
R
}
=
{{
q
0
}
,
{
q
1
,
q
2
}
,
{
q
3
,
q
4
}
,
.Toconstruct
Q
(
k
+
1
)
2
from
Q
(
k
)
2
{
q
1
,
q
2
,
q
5
}
,
q
R
}
, we form the subset of
Q
1
that can be
reached on each input letter from a subset in
Q
(
k
)
2
, as illustrated above. If this is a new set,
it is added to
Q
(
k
)
2
2
and
Q
(
k
+
1
2
are the same, we terminate
this process since no new subsets of
Q
1
can be reached from
s
1
. This process eventually
terminates because
Q
2
hasatmost2
|Q
1
|
elements. It terminates in at most 2
|Q
1
|
−
to form
Q
(
k
+
1
)
2
.When
Q
(
k
)
1steps
because starting from the initial set
at least one new subset must be added at each step.
The next-state function
δ
2
of
M
2
is defined as follows: for each state
q
of
M
2
(a subset
of
Q
1
), the value of
δ
2
(
q
,
a
)
for input letter
a
is the state of
M
2
(subset of
Q
1
) reached from
q
on input
a
.Asthesets
Q
(
1
)
2
{
q
0
}
,
...
,
Q
(
m
)
2
are constructed,
m
≤
2
|Q
1
|
−
1, we construct a
table for
δ
2
.
We now show by induction on the length of an input string
z
that if
z
can take
M
1
to
a state in the set
S
Q
1
,thenittakes
M
2
to its state associated with
S
. It follows that if
S
contains a final state of
M
1
,then
z
is accepted by both
M
1
and
M
2
.
The basis for the inductive hypothesis is the case of the empty input letter. In this case,
s
1
is reached by
M
1
if and only if
⊆
is reached by
M
2
. The inductive hypothesis is that
if
w
of length
n
can take
M
1
to a state in the set
S
,thenittakes
M
2
to its state associated
with
S
. We assume the hypothesis is true on inputs of length
n
and show that it remains
true on inputs of length
n
+
1. Let
z
=
w
a
be an input string of length
n
+
1. To show
that
z
can take
M
1
to a state in
S
if and only if it takes
M
2
to the state associated with
S
,
observe that by the inductive hypothesis there exists a set
S
{
s
1
}
Q
1
such that
w
can take
M
1
to a state in
S
if and only if it takes
M
2
to the state associated with
S
. By the definition
of
δ
2
, the input letter
a
takes the states of
M
1
in
S
into states of
M
1
in
S
if and only if
a
takes the state of
M
2
associated with
S
to the state associated with
S
. It follows that the
inductive hypothesis holds.
⊆
Up to this point we have shown equivalence between deterministic and nondeterministic
FSMs. Another equivalence question arises in this context: It is, “Given an FSM, is there an
equivalent FSM that has a smaller number of states?” The determination of an equivalent FSM
Search WWH ::
Custom Search