State machines redux (link dump)

I started digging around looking for some good examples of state machines to test with, and found a bunch of stuff. (And I could swear that I'd already written this post, but ... apparently not.)

State machines are used for simple sentence parsing. Turns out they're not powerful enough to do the job in all cases (which I knew, but coming at a topic from another angle always allows me to be surprised again and again). However, they've been used pretty successfully for extraction of noun phrases and names from newsfeeds, which is kind of interesting.

Here's a kind of fun approach (though Java-based) to FSMs, using the example of a kind of treasure-hunt game. A state machine lends itself well to Zork-like games.

Here's a tutorial from a robotics approach, although not one I find all that convincing. State machines are, however, very commonly used for robotics controllers, for the obvious reasons. There is lots of material about compiling state machines onto microcontrollers. So my original reason for looking about state machines, WWW::Mechanize, makes a lot of sense. A state machine is a natural way of describing the actions of an agent.

Here's a Ruby/Rails state machine plugin, with good examples.

There's a guy in St. Petersburg who has coined the term "Automata-based programming".

An interesting application of a state machine in building a tree from a serialized protocol.

Charming Python has a chapter on state machines, particularly focused on text processing (e.g. generating HTML from Wiki, which is a good example).

And that's pretty much my link dump. Not a lot of coherence.

Update 11/17/11: I did a little more thinking on this topic.