Good Math

The Simplest Machine

Finite state machines are very limited. They can’t count, and they can’t recognize deep or nested patterns. They really don’t have much in the way of computational power. But they’re still very useful. Every modern programming language has finite state machines in the form of regular expressions built in or provided by a library.

So let’s look at how the machines work. A finite state machine really only does one thing: it looks at a string of characters and determines whether or not that string of characters fits some pattern. To do this, the machine has a small piece of state consisting of a single atomic value, called the state of the machine. When it’s performing a computation, the FSM is allowed to look at exactly ...