What is a state machine? (2023)

A state machine is a behavior model. It consists of a finite number of states and is therefore also called finite-state machine (FSM). Based on the current state and a given input the machine performs state transitions and produces outputs. There are basic types like Mealy and Moore machines and more complex types like Harel and UML statecharts.

This introduction gives a short overview of the common basis and the differences between state machine types.

What is a state machine? (1)

Simple state machine

The basic building blocks of a state machine are states and transitions. A state is a situation of a system depending on previous inputs and causes a reaction on following inputs. One state is marked as the initial state; this is where the execution of the machine starts. A state transition defines for which input a state is changed from one to another. Depending on the state machine type, states and/or transitions produce outputs.

(Video) What is a State Machine?

Consider the simple state machine above. It consists of two states, Off and On. On is the initial state here; it is activated when the state machine is executed. The arrows between the states denote the possible state transitions. They define for which input a state change occurs. Here, the active state is changed from On to Off for the input buttonpressed, and back again to On for the same input.

Please note: In automata theory an automaton reacts on inputs and produces outputs. There, the terms input and output are usually used for symbols which belong to an alphabet. Modern state machines use an extended definition of inputs and outputs. Inputs can be events like a button click or a time trigger while outputs are actions like an operation call or a variable assignment.

In the following, we will extend the simple switch example to explain the differences between Mealy and Moore machines as well as Harel statecharts and UML state machines.

Moore machines

In automata theory, there are two basic types of finite-state machines (FSM). One of those is called Moore machine, named after its inventor Edward Moore, who introduced the concept in 1956. Moore machines consist of states and transitions. States are able to produce outputs, and the output is determined solely by the current state, not by any input.

We extend the switch example above into a light switch with different brightness levels. The light switch has two buttons, an ON button and an OFF button. Pressing the ON button switches the light on and toggles through the different brightness levels. This behavior is modeled by the state machine below. Pressing a button raises a corresponding event (ON_pressed or OFF_pressed) upon which the machine reacts with a state change and corresponding outputs. The output of the state machine is simply the brightness level. As in Moore machines only states produce outputs, we need one dedicated state per brightness level:

What is a state machine? (2)

Light switch example as a Moore machine, modeled with itemis CREATE

Mealy machines

Mealy machines were invented by George H. Mealy in 1955. In comparison with Moore machines, Mealy machines produce outputs only on transitions and not in states. This often results in state diagrams with fewer states because more logic can be put on transitions.

(Video) Understanding State Machines, Part 1: What Are They?

What is a state machine? (3)

Light switch example as a Mealy machine

Be aware that both state diagrams, the Moore machine above and the Mealy one, describe exactly the same system. Indeed, automata theory states that you can always translate a Moore machine into a Mealy machine and vice versa, without losing any expressiveness.

Harel statecharts

Although Mealy machines can already reduce the number of required states, for complex systems such automatons get easily unmanageable. Or to put it in David Harel’s words:

"A complex system cannot be beneficially described in this naive fashion, because of the unmanageable, exponentially growing multitude of states, all of which have to be arranged in a ‘flat’ unstratified fashion, resulting in an unstructured, unrealistic, and chaotic state diagram."

Harel concluded that "a state approach must be modular, hierarchical and well-structured" and introduced additional concepts like state composition and orthogonality.

He coined the term “statechart”, and defined it as:

"statecharts = state-diagrams + depth + orthogonality + broadcast communication"

So basically Harel statecharts are Mealy/Moore machines extended by further concepts that allow us to model complex systems in a practical way.

(Video) #35 State Machines Part-1: What is a state machine?

Using composite states and sub diagrams, we are able to bring more depth into state diagrams, while keeping the diagrams clear and well-structured. Regions help us to express orthogonality: Different substate machines that can be executed side by side. Events allow us to achieve broadcast communication and give us a strong means to describe complex behavior. Using guards, we can state that a certain event triggers a transition only if a given condition is met. Inter-level transitions, history states, temporal logic as well as entry, exit and throughout actions are further Harel statechart elements.

Harel statecharts can define variables which can be used in input and output expressions. Regarding the light switch example, this allows us to store the brightness level in a variable instead of a number of states. In that way, we can simplify the statechart by merging all Light On states into one and executing the output actions on a self-transition. Here we just increment the brightness value each time the transition is taken. We use the modulo expression to ensure the brightness value stays between 1 and 3. This has the benefit that we can change the number of brightness levels without adding new states.

What is a state machine? (4)

Light switch example as a Harel statechart

To showcase the use of composite states we extend the light switch example by a motion detection mode. When the MOT button is pressed, the motion sensor is activated. Once the sensor detects any motion (event motion_detected), the light is switched on at the highest brightness level (brightness = 3). This can be modeled with a composite state that groups the two states Motion Detected and No Motion Detected together.

What is a state machine? (5)

Extended light switch example as a Harel statechart with composite states

Please also note that Harel statecharts combine the characteristics of Mealy and Moore machines, hence outputs can be produced by states as well as transitions as indicated in the statechart above.

We can even go one step further and hide the logic of the Motion Detection Mode into a sub diagram. In that way, the system gets more comprehensive as one can directly see the different modes and how to switch between them.

What is a state machine? (6)

(Video) Finite State Machines explained

Extended light switch example as a Harel statechart with sub diagrams

Further concepts like orthogonality or history states are left out here for brevity. You can read about them in our quick reference.

The present age: UML state machines

UML state machines are based on the statechart notation introduced by David Harel. Furthermore, the UML extends the notation of Harel statecharts by object-oriented principles. Mapping this to our light switch example, in UML we can model the possible actions of the light switch as a type with operations turnOn(), turnOff(), setBrightness(value) and so on.

The following table illustrates the differences between the previously described types at a glance:

What is a state machine? (7)

Differences between the state machine types

Learn more about modeling systems with state machines in our free whitepaper:

The statechart examples of this article were designed with itemis CREATE":https://www.itemis.com/en/yakindu/state-machine/, whose documentation you are reading just now. Create statecharts are based on Harel statecharts and are very close but not identical to UML state machines. The concrete differences are explained in the documentation where they exist. itemis CREATE comes with a statechart simulator which allows to directly execute the modeled statecharts. Various code generators translate the statechart into source code.

What is itemis CREATE?

(Video) Computers Without Memory - Computerphile

FAQs

How do you define a state machine? ›

A state machine is a mathematical abstraction used to design algorithms. A state machine reads a set of inputs and changes to a different state based on those inputs. A state is a description of the status of a system waiting to execute a transition.

What is an example of a state machine? ›

There are many more examples of finite state machines we could use: a vending machine. a subway entrance turnstile. a heating system.

What is the function of a state machine? ›

A state machine is any device storing the status of something at a given time. The status changes based on inputs, providing the resulting output for the implemented changes. A finite state machine has finite internal memory.

What are types of state machines? ›

Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one.

What are the 3 main parts of a state machine? ›

A Finite State Machine (FSM) consists of these parts:
  • State: Each state is represented as a bubble. ...
  • Input Alphabet: These can represent events, characters, etc. ...
  • Labeled Arrows: An arrow connects from one state to another (or back to itself), and is labeled by something from the input alphabet.
Oct 14, 2020

What are the two types of state machines? ›

There are two types of finite state machines (FSMs): deterministic finite state machines, often called deterministic finite automata, and non-deterministic finite state machines, often called non-deterministic finite automata.

Is a PLC a state machine? ›

By using state machine programming techniques, however, PLC programs can become very simple to create, and are easy to maintain and modify. A state machine model is a programming paradigm wherein the "machine" (i.e.: the controller) can only ever be in one of a set of distinct states (conditions) at any given time.

How to make a state machine? ›

Creating a state machine
  1. In the Project Explorer, right-click the model and select Add UML > Package.
  2. Enter a name for the new package. For example, Finite State Machines.
  3. Right-click the package and select Add UML > State Machine.
  4. Enter a name for the new state machine. For example, FTM State Machine.

Why computer is a state machine? ›

A computer is nothing but a state machine. It has registers and memory (state) which contain values that change over time as its operations are executed (state transitions). A programming language is a way to describe a class of state machines.

What is a state machine definition AWS? ›

A state machine is a workflow. A task is a state in a workflow that represents a single unit of work that another AWS service performs. Each step in a workflow is a state.

How do you describe a state machine diagram? ›

The state machine diagram is also called the Statechart or State Transition diagram, which shows the order of states underwent by an object within the system. It captures the software system's behavior. It models the behavior of a class, a subsystem, a package, and a complete system.

What is meant by state machine model? ›

A state machine model is a mathematical model that groups all possible system occurrences, called states. Every possible state of a system is evaluated, showing all possible interactions between subjects and objects. If every state is proven to be secure, the system is proven to be secure.

Videos

1. Mealy and Moore State Machines (Part 1)
(Neso Academy)
2. What is State Machine in UiPath with Example
(Automate with Rakesh)
3. How to Program in Unity: State Machines Explained
(iHeartGameDev)
4. UML State Machine Diagram
(Ave Coders)
5. Getting your act together with State Machines
(Zen of Coding)
6. Finite State Machine (Finite Automata)
(Neso Academy)
Top Articles
Latest Posts
Article information

Author: Fredrick Kertzmann

Last Updated: 03/17/2023

Views: 5447

Rating: 4.6 / 5 (66 voted)

Reviews: 89% of readers found this page helpful

Author information

Name: Fredrick Kertzmann

Birthday: 2000-04-29

Address: Apt. 203 613 Huels Gateway, Ralphtown, LA 40204

Phone: +2135150832870

Job: Regional Design Producer

Hobby: Nordic skating, Lacemaking, Mountain biking, Rowing, Gardening, Water sports, role-playing games

Introduction: My name is Fredrick Kertzmann, I am a gleaming, encouraging, inexpensive, thankful, tender, quaint, precious person who loves writing and wants to share my knowledge and understanding with you.