Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

NFA to DFA program

by Anonymous Monk
on Jan 27, 2000 at 22:27 UTC ( #2511=perlquestion: print w/replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

For all you computer science theory people how much work would it be to write an NFA to DFA converter in Perl and do any of you have any suggestions as to what approach you might take?

Replies are listed 'Best First'.
Re: NFA to DFA program
by Crulx (Monk) on Feb 15, 2000 at 20:04 UTC
    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.
Re: NFA to DFA program
by Anonymous Monk on Jan 30, 2000 at 03:22 UTC
    Most conversions I've seen of NFA's to DFA's are ugly. THey involve cross multiplying the states so you get a huge state table for your DFA. I dont know why all the texts use this awful approach but I developed a much faster one when forced to do this conversion on a test. In the resultant DFA most of the nodes are never visited...the quickest way to find the DFA is to start with the NFA start point and only consider those nodes that it is possible to visit giving your rules.
RE: NFA to DFA program
by setantae (Scribe) on Jan 28, 2000 at 04:17 UTC
Re: NFA to DFA program
by stephen (Priest) on Jan 28, 2000 at 03:37 UTC
    Okay, I'll admit ignorance-- what do NFA and DFA stand for?
      Nondeterministic Finite Automata
      and Deterministic Finite Automatat

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://2511]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (10)
As of 2016-09-26 18:48 GMT
Find Nodes?
    Voting Booth?
    Extraterrestrials haven't visited the Earth yet because:

    Results (488 votes). Check out past polls.