Finite State Machines
A finite state machine is a computer that can only be in one state at a given time.
Some common examples of finite state machines in daily life are vending machines, elevators, traffic lights, combination locks, and turnstyles. John Conway also uses a finite state machine to explain how his esolang FRACTRAN works in this video.
A finite state machine consists of multiple states, can accept multiple different types of inputs, and has a set of transitions to move from state to state based on those inputs.
A state in a finite state machine is a resting place, where the machine waits for specific inputs to make it's next transition.
In low-level computing, a bit can have two states:
1. In something like a combination lock, the different states could be:
waiting for first number
correct first number/waiting for second number
correct second number/waiting for third number
In each of these states, the input and how the machine will react to them changes.
There is also a higher level state of the combination lock:
unlocked, with it's own set of inputs. A finite state machine can and usually does have multiple layers of state to create complex mechanisms.
An input can be anything that causes the finite state machine to transition states.
For a combination lock, one of the inputs is the dial, and another input is the U-bar. Each of these inputs are independent of one another and can both affect the state of the lock itself.
A transition is what occurs when a given input occurs while in a given state.
For instance, with a dial as our input, rotating the dial right to the correct first number will cause the state to transition from
waiting for first number to
correct first number/waiting for second number. An incorrect first number will do nothing, causing no transition. Similarly, using the correct second number while in the
waiting for first number state will do nothing, as the inputs rely completely upon which state the finite state machine is currently in to make a transition.
Another input for the combination lock is the U-bar on the lock. Pulling up on the lock when in the
correct combination state will unlock the lock, transitioning the state of the lock to go from
unlocked, as well as from
correct combination to
waiting for first number. Pulling up when not in that state will cause the U-bar to do nothing, as the state.
Finite state machines are often represented in a table, with one axis being your current state and the other axis being the received input. Here, the states are along the top, with inputs along the left. Notice how each input has a different effect depending on which state it is currently in.
|Start/Waiting for First||Waiting For Second||Waiting For Third||Correct Combination|
|Correct First Number||Waiting For Second||Start||Start||Start|
|Correct Second Number||Start||Waiting For Third||Start||Start|
|Correct Third Number||Start||Start||Correct Combination||Start|
|Multiple rotations to the right||Start||Start||Start||Start|
Last modified: 202204200016