---

title: State machines created_at: 2022-08-26T14:52:16.823Z updated_at: 2022-08-26T14:52:16.823Z tldr: start, do, repeat, end is_published: 1 star: false category: Technical, Machines share_type: share

In mathematics, states describe the conditions of a system. A state machine reads inputs and changes to a different state based on those inputs. In defining an object or a program states help in breaking down complex flows into simple understandable states.

Finite state machines

FSM can be in exactly one of a finite number of states at any given time. The states can change from one state to another in response to the input. The state change is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.

Elevators are a simple example. Say in rest we press a button to a floor, and the elevator moves to that floor and gets back to rest.

Deterministic FSM

For any given input, we can determine the state to which the machine will move next. So it's a deterministic machine. And the machine can move to exactly one state at a time. At any given input the machine cannot be in two possible states. Almost all real-world systems are Deterministic.

These machines process, and when it gets to the end it's true or false for an external trigger to happen. A vending machine reads the coin input and does the processing of validating the coin and either dispenses a soda can or rejects the coin.

Non-deterministic FSM

For any given input there can be more than one state. Which is Non-deterministic. Say we want a pattern-matching system, which starts with any number of a and ends with b or c. so all the valid strings are aaab, abc, aaaccccb, acb. Now the state machine representing it will be

Our pattern machine has 2 non-deterministic states, without the look ahead, it can end up in either of the states. So if it ends up in the wrong state how to proceed? Backtrack.

By nature, all non-deterministic machines can be converted to deterministic machines. But by doing so the complexity increases. A non-deterministic machine can produce a really big deterministic machine.

Our non-deterministic pattern machine has 4 states and 6 transitions. Our deterministic machine has 5 states and 7 transitions.

Infinite state machines

A machine as complex as the universe or a person that goes on from one transition to another. An infinite state machine is simply a state machine with an uncountable number of states and transitions. It can be built but is not practical or useful in operations. Oh, what about simulating a universe? Yes, it is a finite state machine but the actual one has induced randomness which leads to a state not defined, so we really can't build one.

Where can I use this

All machines can be defined in finite states. For the purposes of demonstration, let's build an email input field. It is a basic string acceptor with an email validator and some other validators. It has accepted, invalid and checking states. Let's draw out the transitions between them.

Further reading

• Finite state machines
• Transition system