Geek asks and answers

Data structure for representing automata

I'm currently trying to create a data structure that meets the needs of two machine learning algorithms that I would like to implement in Haskell: RPNI and EDSM .

Intuitively, something close to the fact that zippers for trees would be ideal: these algorithms are state merging algorithms that support some kind of focus (Blue Fringe) on states and, therefore, will benefit from some kind of fasteners lightnings to quickly reach interesting points, But I'm a little lost, because DFA (Definist Finite Automaton) is more like a graph than a tree structure: transitions can make you return to the structure, which is unlikely to make lightnings in order.

So my question is: how would you represent the DFA (or at least its transitions) so that you can quickly manipulate it?

+5
source share
4 answers

Can I use a chart to get started? I think the fgl package is part of the Haskell platform.

Otherwise, you can try to define your own structure using “receive (data)” and use the “Cancel your lightning” library to get the Zipper.

+5
source

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

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

, . , . . , . . , , , :

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

. , . , -.

+9

- , DFA Map State State. . , .

0

regex-tdfa: http://hackage.haskell.org/package/regex-tdfa

The source is quite complex, but it is an implementation of regular expressions with DFA labeled tuned for performance, so it should demonstrate some good practices for representing DFA effectively.

0
source

More articles:


All Articles