Part 2 of what’s becoming my NaCreSoMo 2014 CS mini-tutorial. Last time we talked about lexers; today I want to step away from code and talk about some ideas in computer science that will help build up to where this project is going. Today’s topic is state machines.¹

So, what is a state machine?

Well, here’s a very simple one:

You can think of a pedestrian crossing signal as having three kinds of states: STOP, WALK, and the various COUNTDOWN states. The state just means “what the current conditions are”, which determines what to show on the actual light. The arrows between states are called transitions, and tell you under what conditions you can move to a new state.

This state machine’s not so interesting, though, because it basically operates on its own. Sure, the “STOP → WALK” transition might have something to do with “pressing the cross button”, but it also might just be on a timer. (No matter what, it’s synched up with the rest of the traffic light system at the intersection!) A more interesting state machine is one where you actually have some input on what happens.

So here’s a more interesting one: imagine the state is your current location, and the transitions are directions you can walk. If you’re at the Westfield Mall in San Francisco (state “Market and 5th”), your current state might look like this:

And if you take the transitions “northeast, north, north, north”, you’ll end up at the “Powell and Geary” state, also known as the southwest corner of Union Square.

There are an awful lot of states in this machine (every intersection in San Francisco!), but only a few transitions per state. Not all transitions are valid everywhere, either: you can’t go “east” from “Broadway and Embarcadero” because you’d end up in the bay, and you can’t go “up” from anywhere. (Although sometimes it feels like it.) If someone tried to give you directions that included either of these invalid transitions, you’d reject them—maybe not in advance, but once you got to “Broadway and Embarcadero” you’d certainly realize there was a problem.

Okay, got the idea? A state machine is just a collection of states and transitions, with some known start state. When you “run” it, you keep track of your current state and its transitions, and then just pick the transition that matches the next thing in your “input”. Again, that means the input is basically your “directions” around the “map” of states.

Next time, we’re going to try to use some more abstract state machines to decide if something looks like an e-mail address.

Map images from OpenStreetMap. Diagrams created in Keynote.

This entry was posted on March 19, 2014. Tags: Computer science, NaCreSoMo 2014