In general, there is an equivalence between deterministic finite automata (DFA), nondeterministic finite automata (NFA) and classical computer science regular expressions.

Hmm. Well, i realize you said "in general" but i would like to clarify what to me is an oversimplification. Yes you are correct that there is an equivelence between NFA's and DFA's. More specifically it is always possible to construct a functionally equivelent DFA from and NFA and vice versa (although it is quite possible that an NFA that can comfortably fit in memory cannot be converted to a DFA that will fit in memory). However there is not such an equivelence between FA's and regular expressions. Instead the relationship is asymetrical. Any regular expression matcher can be implemented as an FA (this is obvious as _any_ Finite Automated Interepreted System aka digital computer program can be implemented as an FA) but it is not true that any FA can be implemented using regular expressions. Consider that if it were it would be possible to write _any_ program using regular expressions.

If you want to walk the FSA graph on your own, then in addition the DFA modules mentioned above, it will pay to check out the Graph modules.

In my experience the graph modules scale poorly. I think that for a DFA of some nontrivial size the graph modules would choke.

Despite my criticisms I see the point you were making and do consider it to be a worthy contribution.

regards,

Yves / DeMerphq
---
Writing a good benchmark isnt as easy as it might look.

In reply to Re: Re: Finite State Automata / Transducers by demerphq
in thread Finite State Automata / Transducers by pike

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.