Finite automaton in Haskell
automaton, haskell, representation, state-machine
Solution
There are two basic options:
- An explicit function `delta :: Q -> X -> Q` (or `[Q]` as appropriate) as Sven Hager suggests.
- A map `delta :: Map (Q, X) Q` e.g. using `Data.Map`, or if your states/alphabet can be indexed by ascending numbers `Data.Array` or `Data.Vector`.
Note that these two approaches are essentially equivalent, one can convert from the map version to a function version (this is slightly different due to an extra `Maybe` from the `lookup` call) relatively easily
delta_func q x = Data.Map.lookup (q,x) delta_map
(Or the appropriately curried version of the look-up function for whatever mapping type you are using.)
If you are constructing the automata at compile time (and so know the possible states and can have them encoded as a data type), then using the function version gives you better type safety, as the compiler can verify that you have covered all cases.
If you are constructing the automata at run time (e.g. from user input), then storing `delta` as a map (and possibly doing the function conversion as above) and having an appropriate input validation that guarantees correctness so that `fromJust` is safe (i.e. there is always an entry in the map for any possible `(Q,X)` tuple and so the look-up never fails (never returns `Nothing`)).
Non-deterministic automata work well with the map option, because a failed look-up is the same as having no state to go to, i.e. an empty `[Q]` list, and so there doesn't need to be any special handling of the `Maybe` beyond a call to `join . maybeToList` (`join` is from `Data.Monad` and `maybeToList` is from `Data.Maybe`).
On a different note, the alphabet is most definitely necessary: it is how the automaton receives input.
Problem
What is a good way to represent finite automaton in Haskell? How would the data type of it look like? In our college, automata were defined as a 5-tuple ``` (Q, X, delta, q_0, F) ``` where Q is the set of automaton's states, X is the alphabet (is this part even necessery), delta is the transition function taking 2-tuple from (Q,X) and returning state/-s (in non-deterministic version) and F is the set of accepting/end states. Most importantly, I'm not sure what type `delta` should have...