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

This means if the string is empty, we stay at the state we're at; if not, we follow the first character (by using delta), and then follow the rest of the string from there; this recursive definition maps nicely to a List in scala (or any other language with cons-style lists :), so we end up with the following code:

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 :)

## No comments:

## Post a Comment