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

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.