The state of finite state machine is a mutable variable.

Assume:

• State - type denoting states
• Char - denotes symbols of alphabet

Behavior is given by a big array delta

delta : Array[State,Array[Char,State]]

the initial state is q0.

When in state q and reading symbol c, value delta(q)(c) gives new state:

q = delta(q)(c)

So, next state is computed by table lookup.

Final state can be given by a set or an array

F : Array[State,Boolean]

Essentially, we build an interpreter for finite state machine programs

• q0, delta, F - abstract syntax for finite state machine programs

Previous approach describes an interpreter for finite state machines.

What would a compiler look like?

What do compiled finite state machine descriptions look like?

Finite state encoded as program point.

For arbitrary transitions need to jump to arbitrary program counter.

• need general gotos (jumps)

This implicit encoding of state is what we use (at least partly) in manually constructed lexers.