O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required