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
- Concepts
- Deterministic Finite Automatons (DFAs)
- Non-deterministic Finite Automatons (NFAs)
- Mealy Machines
- Moore Machines
- Statecharts
- Libraries
- JavaScript
- Java
- Python
- Ruby
- Go
- C++
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:
- A finite number of states.
- A finite number of events.
- An initial state.
- 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.
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
- Finite-state_machine
- Theory of Computation - Finite State Machines
- Finite State Machines
- Elements of Robotics - Finite State Machines
- Finite State Machines
- The Rise Of The State Machines
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
- Deterministic finite automaton
- Deterministic Finite Automata (DFAs)
- Deterministic Finite Automata (DFAs)
- Deterministic Finite Automata (DFA)
- Deterministic Finite Automaton
- Deterministic Finite Automata
- Applications of Deterministic Finite Automata
- Deterministic Finite Automata (DFA)
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
- Nondeterministic finite automaton
- Non-deterministic Finite Automata
- Nondeterministic Finite Automata
- Non-deterministic Finite Automaton
- Nondeterministic finite automata
- Nondeterministic Finite Automata
- Non-deterministic Finite State Machines
- Nondeterministic Finite Automata
- NFA (Non-Deterministic finite automata)
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
- Mealy machine
- Mealy Machine
- Mealy machine
- Mealy machine
- Mealy state machine
- Inferring Mealy Machines
- Moore and Mealy Machines
- Mealy and Moore Machines in TOC
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
- Moore machine
- Moore Machine
- Moore Machine
- Moore Finite State Machine
- Moore and Mealy Machine Design Procedure
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
- Welcome to Statecharts
- Statecharts: A Visual Formalism for Complex Systems
- Statecharts
- The Statecharts Perspective
Libraries
JavaScript
- XState
- jssm
- JavaScript State Machine
- Machina
- React Automata
- Robot
- Stately
- Stent
- fsm-as-promised
- redux-machine
- State Machine
- redux-dsm
- nanostate
- kingly
- state
- finity
- mood
- maquinaria
- Statebot
Java
- squirrel-foundation
- Spring Statemachine
- stateless4j
- EasyFlow
- StatefulJ
- Easy States
- JState
- Engine
- Fettle
- Yatomata
- stateful
- state-machine
Kotlin
Python
- transitions
- RAFCON
- django-fsm
- automat
- state_machine
- xworkflows
- django-states2
- python-statemachine
- machinist
- fluidity
- automaton
- pysm
- declarative-fsm
- automaton
Ruby
- aasm
- state_machine
- statesman
- finite_machine
- state_machines
- transitions
- stateful_enum
- micromachine
- workflow
- stately
- motion-state-machine
- aquam
Go
- fsm
- transition
- stateless
- fsm
- stateful
- ws-machine
- fsm
- statemachine-go
- go-sm
- go-fsm
- go-fsm
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.
