The [GoF] State Pattern is a quite well-known design pattern that helps controlling an objects behavior by changing its internal state. Normally you would define a State interface that defines a couple of state transitions as methods, where each method returns a State instance that represents the new state after the transition has been performed. Then you would encapsulate the behavior of each state in concrete interchangeable implementations of the State interface.
An often referred to example is a TCP connection where methods like Open(), Close() and so forth behave differently according to the state of the connection (i.e. the concrete State implementation that the state machine is currently using). Below is the class diagram of the TCP connection example used in the GoF Design Patterns book. As you can see in the class diagram, each state is modeled as a separate class.
There might be cases, however, where you have lots of different states or they might simply not be as clearly defined as in the TCP connection case above (hint: that's probably the case if you go "hmm... how the hell should I name state number 421?!?"). Or there might be cases where you just don't know your states at the time your writing your code, because your state machine will be created by some runtime input (in that case you probably also don't care about explicit state names).
Still, even in these cases just described the idea of the State Pattern can be used. Instead of implementing state behavior in different classes, however, we create instances of a generic State class and configure each instance's behavior by adding transitions to it that are valid for the particular instance. Transitions are modeled as a generic Transition class, which is a two-tuple consisting of a transition symbol (represented as an Object) and the new State instance the transition symbol will lead to. I have illustrated the relationships of the classes below.
First, a client creates a number of State instances, probably marking some of them final. Then it creates some Transition instances and adds them to selected State instances. Finally, it creates a StateMachine by passing it a reference to the initial State. Subsequently, the StateMachine can be used to step through the state space and validate input words. If the StateMachine's Step() method is called, it internally delegates the call to its current State instance, which checks if a Transition with the given transition symbol (i.e. the Object parameter) has been previously defined. Depending on this the method will return the new State instance defined by the Transition or throw an exception. If the method returns successfully, the StateMachine updates its current state accordingly and waits for the next transition to be performed.
Note that in the above diagram the State class does not publicly expose canStep() and step() methods. This is because clients use this class to construct the state space only. For stepping, however, they must use the operations provided in StateMachine.
Using this pattern, it is very easy to create a fast-stepping state machine implementation. Using, for example, a HashTable to look up the Transitions of a State given a certain transition symbol, we can easily create a state machine that steps in O(1) time; because all it takes is looking up the Transition in the HashTable.
If we want, we can add further optimizations to the state machine. For example upon creating it we probably want to remove potential non-deterministic transitions or get rid of equal states, dead-end states, and so forth. And that's where the fun begins =)
Summary: By slightly twisting the original idea of the State Pattern, we can use it to build generic fast-stepping state machines.