Finite state machine

A finite state machine (FSM) is a kind of digital circuit, (and, possibly, other types of machines, including virtual ones) that is used to process information in steps (states). At every state a different part of the information can be processed. This has many advantages in terms of reduced hardware requirements over combinational logic networks (CLNs). See hardware/speed tradeoff. A computer is a (very sophisticated) FSM.

There are several important parts of an FSM:

                                       +------+
        +----------------------------->|Output|---> Outputs
        |  +-----+                     |CLN   |
Inputs -+->|Next | Control             |      |
           |State| Signals     +--+    |      |
        +->|CLN  |------------>|DQ|-+->|      |
        |  +-----+             |  | |  +------+             
Clock--------------------------|> | |
        |                      +--+ |
        +---------------------------+
         State Variables                 

Note: this is a block diagram of a Mealy Machine shown. See also Moore Machine, Class A Machine, Class B Machine, Class C Machine.

• Input: The input to the FSM can help to determine both the next state and the output. The inputs can either change with the clock, in which case the FSM can be called a synchronous sequential network, or the inputs can change independent of the clock, in which case the FSM is an asynchronous sequential network.
• Output: The output of an FSM is dependent upon the current state and, possibly, the current input. The value of the output variable(s) is determined by the Output Combinational Logic Network (CLN).
• State: The current state of the FSM must be stored somewhere, often in a set of D Flip-Flops, and is usually fed into both the next state logic, and the output logic.
• Control Signals: The control signals are the output of the next state logic, and are fed into the inputs of the D Flip-Flops. On an active clock edge, the value of the control signals becomes the value of the current state.

These devices are said to be causal, and to have memory, as the state of the FSM is dependant not only upon the current input, but also upon past inputs (and thus past states).

See also state assignment, state minimization, state transition table, state transition diagram, digital systems, general purpose computer, one-hot encoding.

The description above suggests that finite state machines are always hardware devices. But they are a mathematical specification of systems behaving in a certain way; such systems can be found not only in digital circuits, but just as well in software, and in the natural world around us.

There is a lot of (mathematical) theory on them. Some of this theory is essential to many courses in computing science, and usually calls them finite state automata.

What this theory considers is the use of these machines as language acceptors. That is, we disregard output, control signals, and clocks entirely, regard one state as the initial state, and another as the final state. We then consider the set of possible input sequences that bring the machine from initial to final state, calling this set the language associated with the machine.

We then consider the question: which languages can be described in this way?

Why is this so important to the construction of software systems? Well, many software systems operate on a finite amount of input. The input must be presented in some kind of structured format, to be read and interpreted by the program. The structured format is the "language". The question really asks whether a task, in order to be performed by a program, requires an input format that can be scanned and interpreted using no more than a fixed amount of memory. If it can, we not only know something about the program - namely, that it is, essentially, a finite state machine - but also something about the input format required - namely, that it is a so-called regular language.

Finite state machines are also used very commonly as a method to describe discrete processes, for instance, the progression of customers through a store. The statecharts formalism, now part of UML, is based on them. Another very common application is to attach probabilities to the state transitions and use them to estimate long-term properties of the system; the most common way to do this is Markov modelling and calls the finite state machines Markov chains.