pike has asked for the wisdom of the Perl Monks concerning the following question:

Dear brethren,

I tried to find modules for Finite State Automata / Transducers. I tried entering FSA, FST, "Finite State", and Finite with the search engines both here and on CPAN, but I couldn't find anything. On the other hand, it is hard for me to believe that there should be no module for such a common thing. Any hints?

Thanks,

pike

Replies are listed 'Best First'.
Re: Finite State Automata / Transducers
by valdez (Monsignor) on Jul 17, 2002 at 13:44 UTC

    May be DFA::Simple is what you are looking for... A search with DFA gives two other modules

    Ciao, Valerio

[reply]
Re: Finite State Automata / Transducers
by demerphq (Chancellor) on Jul 17, 2002 at 12:57 UTC
    You didnt use Super Search did you?

    Try that, I just did and it gives a whack of hits.

    HTH

    UPDATE I think you might find some interesting links on virtualsues homenode.

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

[reply]
Re: Finite State Automata / Transducers
by kvale (Monsignor) on Jul 17, 2002 at 16:00 UTC
    A standard approach to handling finite state automata in perl is to use regexes. In general, there is an equivalence between deterministic finite automata (DFA), nondeterministic finite automata (NFA) and classical computer science regular expressions. Perl regexes have classical regexes as a subset of their operations, so it is possible write any accepting/non-accepting FSA as a perl regex.

    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. They make it very easy to set up a graph structure and execute a program on it. These modules are described in detail in the book "Mastering Algorithms in Perl".

    -Mark

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

[reply]
Re: Finite State Automata / Transducers
by Cine (Friar) on Jul 17, 2002 at 12:56 UTC
[reply]
      Im curious but why do you suggest P::RD? It isnt a FSA in the slightest. In fact it isnt a LR parser at all. (Which are usually implemented as FSM's).

      UPDATE:

      While downvoting is certainly a monks right, id like to register the fact that I see no reason at all for downvoting cine's nodes in this thread. Yeah he was bit abrubt but if you read the advice for downvoting I can see no good reason there why these nodes should be --'d. Downvoting should be reserved for trolls and absolute garbage posts. These nodes while hardly exemplary are neither.

      /rant off

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

[reply]
        Because I thought she/he is going to use it to parse something and knows about FSA/LR parsers from the standard literature and therefore searched for that.

        T I M T O W T D I
[reply]
[reply]

Back to Seekers of Perl Wisdom