comment on

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,
Gryn

In reply to Donuts and DFA's by gryng
in thread Research ideas by Wodin

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


There's more than one way to do things
	PerlMonks