Finite State Machines - Part I
Finite State Machines (FSMs), sometimes known as Finite Automata, underlie many mechanisms used in both computer software and hardware. Examples include computer language parsers, validation mechanisms and they are sometimes used as the basis for the artificial intelligence in computer games. I recently used a simple FSM to monitor user input from a "media player" style user interface.
As the name implies, a FSM is made up of several states - only one of which the machine can be in at any moment. The state of the machine changes over time as fresh input data is passed to it. Input data can be almost anything- text characters, numbers or even complex data structures
Although a FSM can have many states there are 3 that each FSM usually has - to help explain each of these I'd like you to consider the process that goes on when you dial a telephone number.
Start state - When a finite state machine is started it immediately goes into a start state - where it is ready to receive input data but has not yet begun to do so - in our telephone analogy the start state would be the sounding of the dialling tone - this is the telephone system's way of telling you it is ready to receive input.
Junk state - If the finite state machine receives input data that does not allow it to progress to another state then it automatically enters the junk state. The junk state implies that the FSM considers the sequence of data it has received to be invalid. It is because of this strict mechanism that one has to be extremely careful when programming a FSM to consider all possible combinations of valid data so that correct data (no matter how unlikely to occur) is not considered invalid. In the telephone analogy the machine would go into the junk state if you dialled an incorrect number - In the UK, for example, area codes begin with 01*** - and the telephone system would enter the junk state immediately if you typed 05. Once a machine has entered the junk state it cannot leave it and the data is considered invalid.
End state - If a finite state machine enters this state then the stream of input data it has received up to this point is considered to be valid. Reaching this state often triggers an event to occur - possibly that the machine should stop processing input data - but quite commonly the machine continues to process input data until it has been exhausted - only if it is then in the end state will it consider the entire sequence of data to be valid. In the telephone analogy entering a valid telephone number would move the telephone system into an end state and the call would be connected.
The following diagram illustrates a FSM that validates positive and negative decimal numbers.
Note that junk states are not included in the diagram.
The machines start state is q0 (the use of 'q' here is just a useful convention for labelling states) and its goal state is q3 (double outlines indicate goal states). Movement to other states is governed by the characters that are contained in the input string. Take, for example, the input string '-12.34' - this would lead to the following sequence of state transitions:
q0 - q4 - q1 - q1 - q2 - q3 - q3
Since the q3 state is a goal state the input string would be classified as valid by this FSM. An example of an invalid input string would be the string '1.2-1' which would lead to the state transition sequence:
q0 - q1 - q2 - q3 - Junk State
This happens because q3 does not have a transition rule for the character '-' so the machine automatically enters the "junk" state.
In the next instalment I'll use the decimal number validator example above to illustrate how to program a FSM using Java.
As the name implies, a FSM is made up of several states - only one of which the machine can be in at any moment. The state of the machine changes over time as fresh input data is passed to it. Input data can be almost anything- text characters, numbers or even complex data structures
Although a FSM can have many states there are 3 that each FSM usually has - to help explain each of these I'd like you to consider the process that goes on when you dial a telephone number.
Start state - When a finite state machine is started it immediately goes into a start state - where it is ready to receive input data but has not yet begun to do so - in our telephone analogy the start state would be the sounding of the dialling tone - this is the telephone system's way of telling you it is ready to receive input.
Junk state - If the finite state machine receives input data that does not allow it to progress to another state then it automatically enters the junk state. The junk state implies that the FSM considers the sequence of data it has received to be invalid. It is because of this strict mechanism that one has to be extremely careful when programming a FSM to consider all possible combinations of valid data so that correct data (no matter how unlikely to occur) is not considered invalid. In the telephone analogy the machine would go into the junk state if you dialled an incorrect number - In the UK, for example, area codes begin with 01*** - and the telephone system would enter the junk state immediately if you typed 05. Once a machine has entered the junk state it cannot leave it and the data is considered invalid.
End state - If a finite state machine enters this state then the stream of input data it has received up to this point is considered to be valid. Reaching this state often triggers an event to occur - possibly that the machine should stop processing input data - but quite commonly the machine continues to process input data until it has been exhausted - only if it is then in the end state will it consider the entire sequence of data to be valid. In the telephone analogy entering a valid telephone number would move the telephone system into an end state and the call would be connected.
The following diagram illustrates a FSM that validates positive and negative decimal numbers.
Note that junk states are not included in the diagram.
The machines start state is q0 (the use of 'q' here is just a useful convention for labelling states) and its goal state is q3 (double outlines indicate goal states). Movement to other states is governed by the characters that are contained in the input string. Take, for example, the input string '-12.34' - this would lead to the following sequence of state transitions:
q0 - q4 - q1 - q1 - q2 - q3 - q3
Since the q3 state is a goal state the input string would be classified as valid by this FSM. An example of an invalid input string would be the string '1.2-1' which would lead to the state transition sequence:
q0 - q1 - q2 - q3 - Junk State
This happens because q3 does not have a transition rule for the character '-' so the machine automatically enters the "junk" state.
In the next instalment I'll use the decimal number validator example above to illustrate how to program a FSM using Java.