Automat is a Clojure and ClojureScript library for defining and using finite-state automata, inspired by Ragel. However, instead of defining a DSL, it allows them to be built using simple composition of functions.
These automata, once compiled, are quite fast. An array with 100 million elements can be processed in 500ms, giving a mean transition time of 5ns. However, Automat isn't just for high throughput use cases; it's meant to be useful wherever an FSM is necessary.
[automat "0.2.4"]
Full documentation can be found here.
A finite-state machine or finite-state automaton is defined as a series of states and transitions between these states, driven by a sequence of inputs. The automaton begins at a start state, and proceeds through the transitions until it reaches an accept state. If given an input that isn't a valid transition, the automaton may either reject the input sequence or reset to the beginning, depending on the use case.
In Automat, the simplest automaton is simply a vector representing a chain of valid inputs.
> (require '[automat.viz :refer (view)])
nil
> (require '[automat.core :as a])
nil
> (view [1 2 3])
The circle on the left is the start state, and the circle on the right with the double-lined border is the accept state. Note that the transitions don't have to be numbers:
> (view [:foo "bar" 'baz])
Each argument to fsm
can either be an input or another automaton.
> (view [1 [2 [3]]])
Note that this is identical to the first automaton. If you want to consume inputs which are vectors without them being flattened, they can be represented as lists:
> (view [1 '(2 (3))])
We can also combine existing automatons using the operators in automat.core
:
> (view (a/or [1 2 3] [1 3]))
This represents the union of the two automata, and returns an automaton which will either accept 1, 2, 3
or 1, 3
.