# Implementing Finite State Machines

## Using an Array

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

## Compiled Finite State Machine

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.