Finite State Automata / Transducers

[pike]

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

[valdez]

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

Ciao, Valerio

[demerphq]

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.

[kvale]

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

[demerphq]

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.

[Cine]

Parse::RecDescent?

T I M T O W T D I

[demerphq]

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.

[Cine]

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

[tadman]

Or it can be reserved for posts which don't make any sense. If an explanation was given in the first place, there'd be no reason to downvote.

I don't see the point in posting quick, pointless responses. -- for Re: Finite State Automata / Transducers and ++ for Re: Re: Re: Finite State Automata / Transducers which actually explains what the rationale was.