Information Technology Reference
In-Depth Information
4.2 Equivalence of DFSMs and NFSMs
Finite-state machines recognizing the same language are said to be equivalent . We now show
that the class of languages accepted by DFSMs and NFSMs is the same. That is, for each
NFSM there is an equivalent DFSM and vice versa. The proof has two symmetrical steps: a)
given an arbitrary DFSM D 1 recognizing the language L ( D 1 ) ,weconstructanNFSM N 1
that accepts L ( D 1 ) ,andb)givenanarbitraryNFSM N 2 that accepts L ( N 2 ) ,weconstructa
DFSM D 2 that recognizes L ( N 2 ) . The first half of this proof follows immediately from the
factthataDFSMisitselfanNFSM.Thesecondhalfoftheproofisabitmoredifficultand
is stated below as a theorem. The method of proof is quite simple, however. We construct a
DFSM D 2 that has one state for each set of states that the NFSM N 2 can reach on some input
string and exhibit a next-state function for D 2 . We illustrate this approach with the NFSM
N 2 = ND of Fig. 4.2 .
Since the initial state of ND is q 0 , the initial state of D 2 = M equiv , the DFSM equivalent
to ND ,istheset
{
q 0 }
. In turn, because q 0 has two successor states on input 0, namely q 1 and
q 2 ,welet
in M equiv on input 0, as shown in the following
table. Since q 0 has no successor on input 1, the successor to
{
q 1 , q 2 }
{
q 0 }
be the successor to
{
q 0 }
on input 1 is the empty set
.
{
q 1 , q 2 }
{
q 3 , q 4 }
Building in this fashion, we find that the successor to
on input 1 is
whereas
. The reader can complete the table shown below. Here q equiv is
thenameofastateoftheDFSM M equiv .
its successor on input 0 is
q equiv
a
δ M equiv ( q equiv , a )
q equiv
q
{
q 0 }
0
{
q 1 , q 2 }
{
q 0 }
a
{
q 0 }
1
{
q 1 , q 2 }
b
{
q 1 , q 2 }
0
{
q 3 , q 4 }
c
{
q 1 , q 2
}
1
{
q 3 , q 4
}
{
q 1 , q 2 , q 5
}
d
{
q 3 , q 4
}
0
{
q 1 , q 2 , q 5
}
q R
{
q 3 , q 4
}
1
{
q 1 , q 2 , q 5
}
0
{
q 1 , q 2
}
{
q 1 , q 2 , q 5
}
1
{
q 3 , q 4
}
In the second table above, we provide a new label for each state q equiv of M equiv .In
Fig. 4.3 we use these new labels to exhibit the DFSM M equiv equivalent to the NFSM ND of
Fig. 4.2 . A final state of M equiv is any set containing a final state of ND because a string takes
M equiv to such a set if and only if it can take ND to one of its final states. We now show that
this method of constructing a DFSM from an NFSM always works.
THEOREM 4.2.1 Let L be a language accepted by a nondeterministic finite-state machine M 1 .
There exists a deterministic finite-state machine M 2 that recognizes L .
Proof Let M 1 =(Σ , Q 1 , δ 1 , s 1 , F 1 ) be an NFSM that accepts the language L .Wedesign
aDFSM M 2 =(Σ , Q 2 , δ 2 , s 2 , F 2 ) that also recognizes L . M 1 and M 2 have identical input
alphabets, Σ .Thestatesof M 2 are associated with subsets of the states of Q 1 ,whichis
denoted by Q 2
2 Q 1 ,where2 Q 1 is the power set of Q 1 containing all the subsets of Q 1 ,
including the empty set. We let the initial state s 2 of M 2 be associated with the set
}
containing the initial state of M 1 .Astateof M 2 is a set of states that M 1 can reach on a
sequence of inputs. A final state of M 2 is a subset of Q 1 that contains a final state of M 1 .
For example, if q 5
{
s 1
F 1 ,then
{
q 2 , q 5
}∈
F 2 .
Search WWH ::




Custom Search