There's more than one way to do things | |
PerlMonks |
Re: NFA to DFA programby Crulx (Monk) |
on Feb 15, 2000 at 20:04 UTC ( [id://3531]=note: print w/replies, xml ) | Need Help?? |
I agree with Mr Anonymous above. Given any
NFA M =(Q,L,d,q0,F)
where Q is the states q0...qn
and L is the Language eg 0, 1, 3
and d is the change table eg q0,"0"->q1
q0 is the start state
F are the goal states.
you can get a DFA M' = (Q',L,d',q0',F') by forming
Q' as the set of all subsets of the Q
That, depending on the size of your Q, will be big...
The monk has a very interesting answer. You basically
have to do this traversal in generating the d'.
Combining the traversal and the state generating would be
interesting. This traversal follows the map of the resulting
DFA so you could concievably combine the steps. All you
would need is a table of pointers to the q' states so if you
generate a q' composite state [qx.. qy... qz] that has
already been traversed, you link to the existing q' state.
So you basically build the DFA's nodes as you go. This would
save greatly on memory use of a complicated NFA.
--- Crulx crulx@iaxs.net
In Section
Seekers of Perl Wisdom
|
|