Data structure to represent automata

Question

I'm currently trying to come up with a data structure that fits the needs of two automata learning algorithms I'd like to implement in Haskell: RPNI and EDSM.

Intuitively, something close to what zippers are to trees would be perfect: those algorithms are state merging algorithms that maintain some sort of focus (the Blue Fringe) on states and therefore would benefit of some kind of zippers to reach interesting points quickly. But I'm kinda lost because a DFA (Determinist Finite Automaton) is more a graph-like structure than a tree-like structure: transitions can make you go back in the structure, which is not likely to make zippers ok.

So my question is: how would you go about representing a DFA (or at least its transitions) so that you could manipulate it in a fast fashion?

Cristencristi

Answer 1

Can you just use a graph to get started? I think the fgl package is part of the Haskell Platform.

Otherwise you can try defining your own structure with 'deriving (Data)' and use the "Scrap Your Zipper" library to get the Zipper.

Skysweeper

Thanks for the suggestion, I'll try to see if it fits my needs :) – Cristencristi

Or just pass in a pair of function containing your custom pred and succ. – Skysweeper

Answer 2

Let me begin with the usual opaque representation of automata in Haskell:

newtype Auto a b = Auto (a -> (b, Auto a b))

This represents a function that takes some input and produces some output along with a new version of itself. For convenience it's a Category as well as an Arrow. It's also a family of applicative functors. Unfortunately this type is opaque. There is no way to analyze the internals of this automaton. However, if you replace the opaque function by a transparent expression type you should get automata that you can analyze and manipulate:

data Expr :: * -> * -> * where
    -- Stateless
    Id      :: Expr a a

    -- Combinators
    Connect :: Expr a b -> Expr b c -> Expr a c

    -- Stateful
    Counter :: (Enum b) => b -> Expr a b

This gives you access to the structure of the computation. It is also a Category, but not an arrow. Once it becomes an arrow you have opaque functions somewhere.

Cuomo

Thanks, it's an interesting answer. However I'm afraid I'm not used enough to use Arrows and Categorys abstractions to really make use of it right now. I'll keep it in a corner though :) – Cristencristi

Answer 3

If you don't need any fancy graph algorithms you can represent your DFA as a Map State State. This gives you fast access and manipulation. You also get focus by keeping track of the current state.

Mariellemariellen

Answer 4

Take a look at the regex-tdfa package: http://hackage.haskell.org/package/regex-tdfa

The source is pretty complex, but it's an implementations of regexes with tagged DFAs tuned for performance, so it should illustrate some good practices for representing DFAs efficiently.

Bankhead