From http://cg.scs.carleton.ca/~michiel/TheoryOfComputation/ (a free ToC book)
Deﬁnition 2.2.1 A ﬁnite automaton is a 5-tuple M = (Q, Σ, δ, q, F), where
1. Q is a ﬁnite set, whose elements are called states,
2. Σ is a ﬁnite set, called the alphabet; the elements of Σ are called symbols,
3. δ : Q × Σ → Q is a function, called the transition function,
4. q is an element of Q; it is called the start state,
5. F is a subset of Q; the elements of F are called accept states.
Doesn't that sound fancy ? It means we have an object with 5 fields (a 5-tuple), Q, a set of things called states, Σ, a set of symbols called the alphabet (we'll use characters as our symbols), δ, a function that takes a state and a symbol and returns a state (conceptually we are 'moving' from one state to another when we see a symbol), q, an element of Q , called the start state and F a subset of Q, the set of accepting states.
In Scala, we can represent it as:
We can then define the extended transition function, which says which state we end up at by following a string, recursively as
And the automata accepts a string if we would go from the initial state to the final state by following that string; in Scala
To use it we would first define a delta function, say:
And then we can use like this:
The full code is at https://github.com/okaram/scala/tree/master/automata, including non-deterministic automata (which I will probably get around to blog about some other time :)