good chemistry is complicated, and a little bit messy -LW |
|
PerlMonks |
Donuts and DFA'sby gryng (Hermit) |
on Feb 20, 2001 at 21:14 UTC ( [id://59714]=note: print w/replies, xml ) | Need Help?? |
By twisting my brain into the shape of a donut, I think I have seen a glimpse of what you mean. Let me see if I have it right:
You propose to turn a regular expresion into a ordered set of states, one for each character position (or possibly no character as well?). This is so that you can go through each atom of each set once (that is, no backtracking, which is the bane of an NFA). This seems (-seems- to someone who has never written an NFA or a DFA before) very similar to a DFA, except that a DFA would not have the order preference that your ordered sets would have, they would just have sets. The consequence to that difference is that with a DFA you can go through each set in parallel, but with the proposed NFA change, you would still have to recurse backwards and forwards. This is -similar- to backtracking, but seems better, because you are going through a finite number of (ordered) sets, and not a possibly geometrically expanding number of states. I may have muddled the nomenculture a bit, sorry :) Ciao,
In Section
Seekers of Perl Wisdom
|
|