The realization of the use of Finite State Machines dates back to the beginning days of computing. The two men first writing about them were Mealy and Moore in the mid fifties. Each had a slightly different view of where the outputs were connected to the state machine, but otherwise had similar views. (Moore thought the state itself made the outputs, and Mealy thought the transition made the outputs, which were then static while in the state.)

The classic text describing Finite State Machines is "Switching and Finite Automata Theory" by Kohavi first published in 1970. While long a regular tool of the hardware designer, it has not been widely known in software circles.

As mentioned Finite State Machines have widely been used to design hardware. You will commonly see them when tough sequencing problems are described. They stand in where flow charts simply become to wild to follow, for instance in describing the bus arbitration in early 68000 documents.

It is very interesting to see the game software had to resort to state machine technology. In retrospect, it almost seems obvious they'd have to given the difficulty in creating Isostructure with in a structured programming environment. Similarly Brooks finds them the preferred way to design behaviors, as described in Mobile Robots.

Some problems just scream for a solution of one kind or another, and Finite State Machines answer many common programming problems better than any other particularly where real time control or process control are involved. So to see the concept discovered and rediscovered over and over again testifies (at least hopefully) to its forecoming popularity.

My experience in working on IsoMax(TM) development over past eight years is: every programmer who makes the paradigm shift, is forever changed, and can never look at one of those intractable IF THEN nests of structured confusion without seeing the essence of the problem, the need for a state machine to simplify and streamline the code. I would strongly recommend robotics users to look into State Machines if you don't know them, or how to program them. There is a huge reward in programming efficiency, and tools to make that even easier (IsoMax(TM)) are now available.

If you can find a copy of the "Feignman Lectures on Computation" you will find an excellent description of FSM's of all types and their relationship with Turing engines. I must say I never really understood how they worked until I read that book.

Here's a link to the book on Amazon:

Feynman Lectures on Computation