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[1]. John Conway also uses a finite state machine to explain how his esolang FRACTRAN works in this video.

Description

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.

States

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: 0 and 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
correct combination

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: locked and 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.

Inputs

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.

Transitions

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 locked to 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.

Representation

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

References

Last modified: 202401040446