Finite State Machine (FSM)

What is Finite State Machine?

Finite State Machine (FSM) is an abstract machine (reffered to as automaton), which is from the Automata Theory of computer science from 20th Century. Simply stated, automata theory deals with the logic of computation with respect to simple machines, referred to as automata

An FSM is abstract since it does not physically exist, and it was invented even before the first computer exists. Through automata, computer scientists are able to understand how machines compute functions and solve problems and more importantly, what it means for a function to be defined as computable or for a question to be described as decidable.

There are four major families of automaton where FSM as one of them: 

  • Finite-state machine 
  • Pushdown automata 
  • Linear-bounded automata 
  • Turing machine

Many things in the real-world are FSMs, e.g., traffic lights are a FSM with several (light) states which will change state when it receives an input, typically just a fixed timer that decides how much time the traffic lights should be green, yellow and red. Also, a turnstile is oftern referred to as an easy example for FSM, where "locked" and "un-locked" are two states, and arrows indicate transitions between states.

from https://www.smashingmagazine.com/2018/01/rise-state-machines/



Example Usages?



An FSM contains 5-tuple $(Q, \Sigma, \delta, q0, F)$ where:
  • $Q$ is a finite set of states, e.g., "locked" and "un-locked" in the above example
  • $\Sigma$ is a finite set of alphabet, e.g., "push" and "coin" in the above example
  • $\delta$ is a transition function: $Q \times \Sigma \rightarrow Q$, which maps states and inputs to another state
  • $q0$ is the initial state which is one of the finite state set $q0 \in Q$ ("locked" in the example)
  • $F$ is the final state(s) which also is(are) in the $Q$ ("unlocked" in the example)

JFLAP is software for experimenting with formal languages topics including FSM.





More formal definition and examples can be found in nice blogs below: