Skip to content

Latest commit

 

History

History
254 lines (189 loc) · 14.1 KB

README.md

File metadata and controls

254 lines (189 loc) · 14.1 KB
Raw


logo of awesome-fsm repository

Awesome Finite State Machines

A curated list of awesome resources related to finite state machines and statecharts.

The main idea of this repository is to have a nice place when people can rely on nice quality content, such as articles, videos, ebooks, documents, books, etc. A little different from the other awesome type lists that we can find in GitHub about a variety of topics, the idea of this list is to provide a nice and short explanation about concepts first, then show a list of nice content related to that specific concept.

Any comments or suggestions about nice quality content that should be in this repository, please open an issue.

Contents

Introduction

You might have not heard the term "finite state machines" before, but humanity has been using this concept every day for a long time. Not only in the programming world, but in real life too, we have a lot of systems that rely upon the concept of finite state machines.

Finite state machines are a computation model, it consists of a machine with a finite number of states. A finite state machine has a finite number of events, to move from one state to another we have something called transitions. These transitions are triggered after a specific event, each transition expects an input, after its triggered, it will change to a specific state depending on the current state and the event.

We can simplify a finite state machine in 4 parts:

  1. A finite number of states.
  2. A finite number of events.
  3. An initial state.
  4. A transition will be triggered after a specific event and will change to a specific state depending on the current state and the event.

Finite state machines can be used to simulate sequential logic, let's take as an example of a traffic light.

We know that a traffic light has only 3 possible states: green, yellow, and red. To change from one state to another, we will use it as an input integer representing seconds. When the input is 60, the machine will trigger an event and transition to another state depending on the current state and the event, in our case, the seconds.

traffic light finite state machine example

We can observe finite state machines not only inside the software development but in our real world as well. You can think about almost anything and use finite state machines for it. By having a finite number of states, it reduces drastically the possibility of having unexpected side-effects in your application, your application will get more consistent, well-written, and maintainable.

Further Reading

Concepts

In the finite state machine model, we have a few different concepts that it’s very important to learn about. There are two types of finite state machines: deterministic state automaton and non-deterministic state automaton. There are a few differences between those two types.

A deterministic state automaton is a finite state machine with a finite number of states and input symbols. A transition is defined in every state for every input symbol. Each input symbol will determine which state the machine will move. A deterministic finite automaton machine can only be in one state at a time, and transition to one state at a time.

A non-deterministic finite automaton has a finite number of states and a finite number of input symbols. In a nondeterministic finite automaton, for each state and input symbol, it can be one or more output states. NFAs can be in one or more states at once.

If you’re wondering, an automaton is the plural of automata. Finite state machines are also known as finite-state automata or finite-state automaton.

Deterministic Finite Automaton (DFAs)

A deterministic finite automaton finite state machine with a finite number of inputs symbols. For each input symbol, it will determine which state the machine will move. A deterministic finite automaton machine can only be in one state at a time, and transition to one state at a time.

Further Reading

Non-deterministic Finite Automaton (NFAs)

A nondeterministic finite automaton has a finite number of states and a finite number of input symbols. In a nondeterministic finite automaton, for each state and input symbol, it can be one or more output states. NFAs can be in one or more states at once.

Further Reading

Mealy Machine

A mealy machine is a machine where the output value is determined by the input and the current state. For each input and state in a Mealy machine, one transition is possible.

Further Reading

Moore Machine

A Moore machine is a machine where the output is determined by only its current state. The output depends only on the present state and it's the same output every time the machine enters that state.

Further Reading

Statecharts

Sometimes we need something more sophisticated and complex, and that's when a finite state machine cannot help us.

Statecharts are an extension of traditional finite state machines, the main difference of statecharts is that it can have a hierarchical state, states can contain nested state inside them. The reason for this is simple, not all applications in the world can be described as flat multi numbers of states, sometimes we need to have nested states.

Statecharts also bring us a few extra features such as actions, entry and exit actions, guard conditions, deferred events, etc.

Further Reading

Libraries

JavaScript

Java

Python

Ruby

Go

Shell

C++

Swift

Contributing

Your contributions are welcome! If you have any content that can contribute to our list, please open a PR.

If there are any questions about this list or about any other topic, please contact me on Twitter @leonardomso and I'll gladly answer it.