Re: Finite State Automata / Transducers

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

Comment on Re: Finite State Automata / Transducers

Replies are listed 'Best First'.
Re: Re: Finite State Automata / Transducers by demerphq (Chancellor) on Jul 18, 2002 at 10:12 UTC
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]

Replies are listed 'Best First'.

Re: Re: Finite State Automata / Transducers
by demerphq (Chancellor) on Jul 18, 2002 at 10:12 UTC

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]