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?
FSMs are also applied polularly used in JavaScript world these days, e.g., a popular library called XState, with more than 14k stars on GitHub. Computer programs are all about transitioning from one state to another after an input. Things can get out of control if you’re not paying close attention, and tools like XState is very helpful to navigate the state complexity as it grows. In computer science, finite-state machines are widely used in modeling of application behavior, design of hardware digital systems, software engineering, compilers, network protocols, and the study of computation and languages.
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:
No comments:
Post a Comment