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?

ertes ertes · Accepted Answer · 2012-05-09T15:00:25

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.

Data structure to represent automata

4 Answers