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.