A topic which often comes up as one gets deeper into computer science is that of finite-state automata. Finite automata are sometimes known as state machines and Richard has talked about concrete implementation considerations already. However an FSM can be used to describe significantly more than you might already think. Learning how to manipulate FSMs can lead to a deeper understanding of several parts of computer science such as lexical analysis, parsing, regular expressions.

In brief, as a data structure, an FSM is a collection of states, a collection of input atoms (also known as the alphabet of the FSM), and a collection of triplets consisting of input state, input, and output state. The vast majority of FSMs you encounter in your day-to-day programming life shall be of the kind in Richard's article, namely deterministic finite state automata. However when one delves deeper into the wonderful world of FSMs, one discovers that more flexible and more easily composed cousin, the non-deterministic finite state automaton or NFA.

The non-deterministic automaton has one specific advantage over its deterministic cousin -- the ability to express indecision through the possibility that a given input atom might transition the NFA to zero, one or more possible states, rather than always to exactly one state.

One further extension of this is needed to give us the most flexible variant of FSMs. This is often called the ε-move and it allows an NFA-ε to transition from one state to another without consuming an input atom at all.

While it's very easy to write code which represents a DFA, and pretty simple to reason about it; reasonably easy to write code which represents an NFA, and not too hard to reason about it; it's pretty hard to write code which usefully represents an NFA-ε and it can be very hard to reason about them.

Fortunately for us, NFA-εs are both helpful, and relatively easy to transform into DFAs later (though that act often expands the storage space required for the FSM quite substantially).

One directly applicable use of building NFA-εs, composing them together, and then converting them to DFAs, is in the construction of regular expression engines. Your homework is to have a look at one of the many descriptions of regular expressions, liken it to an understanding of FSMs from the linked articles on this page, and then have a go at writing a very simple regexp engine for yourself in whatever language you favour. Though I'd recommend using a scripting language if you can, for rapid development and debugging. If you get very stuck you could look to this article for further discussion of FSMs and how to do this.