Okay, I'll admit ignorance--
what do NFA and DFA stand for? | [reply] |

Nondeterministic Finite Automata
and Deterministic Finite Automatat
| [reply] |

| [reply] |

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.
| [reply] |

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 | [reply] |