state machine

In general, a state machine is any device that stores the status of something at a given time and can operate on input to change the status and/or cause an action or output to take place for any given change. A computer is basically a state machine and each machine instruction is input that changes one or more states and may cause other actions to take place. Each computer's data register stores a state. The read-only memory from which a boot program is loaded stores a state (the boot program itself is an initial state). The operating system is itself a state and each application that runs begins with some initial state that may change as it begins to handle input. Thus, at any moment in time, a computer system can be seen as a very complex set of states and each program in it as a state machine. In practice, however, state machines are used to develop and describe specific device or program interactions.

To summarize it, a state machine can be described as:

• An initial state or record of something stored someplace
• A set of possible input events
• A set of new states that may result from the input
• A set of possible actions or output events that result from a new state

In their book Real-time Object-oriented Modeling, Bran Selic & Garth Gullekson view a state machine as:

• A set of input events
• A set of output events
• A set of states
• A function that maps states and input to output
• A function that maps states and inputs to states (which is called a state transition function)
• A description of the initial state

A finite state machine is one that has a limited or finite number of possible states. (An infinite state machine can be conceived but is not practical.) A finite state machine can be used both as a development tool for approaching and solving problems and as a formal way of describing the solution for later developers and system maintainers. There are a number of ways to show state machines, from simple tables through graphically animated illustrations.