Chapter 1.1 · Finite Automata

What is a finite automaton?

A finite automaton is the simplest useful model of a computer. It has a fixed, finite amount of memory — just a current state — and reads its input one symbol at a time, left to right.

Think of an automatic door controller, an elevator, or a vending machine. None of them need to remember the entire history of what happened; they only need to know which state they are in right now. That is exactly the power and the limitation of a finite automaton.

The anatomy of a machine

A machine is drawn as a graph. Circles are states. An arrow coming from nowhere marks the start state. Double circles are accept states. Labeled arrows are transitions: they tell the machine which state to move to when it reads a particular symbol.

The central question
After reading the whole input, is the machine sitting in an accept state? If yes, the string is accepted; if not, it is rejected. The set of all accepted strings is the machine's language.