Good Math

Finite State Machines Get Real

FSMs are great, but if you want to use something like an FSM in a real program, you probably don’t want to try to figure out the whole transition relation and write it all out in code. When we really use a language processed by an FSM, the transition relation contains hundreds of transitions. It’s just hard to write it out correctly. Fortunately, we don’t have to. There’s another way of writing an FSM: regular expressions. If you’re a programmer, you’re almost certainly already familiar with regular expressions: they’re ubiquitous in real programs, and they’re the way that we use FSMs.

Regular expressions aren’t quite a way of writing the FSM. They’re a syntax for writing down the language that an FSM should ...