Introduction
As developers, we often make automation that requires changes from the end user or following conditions we set our programs to run, and in doing so we are making initializations that are ruled by the Finite state machine. This is applied mostly in programming and can also be used in different areas like mathematics, artificial intelligence, design of digital systems, compilers, computational linguistics, and the list goes on.
Today we will learn precisely how it works as well as its variations.
What is a Finite State Machine?
The finite state machine can be seen as a "model" that performs certain computational activities which assume an initial state and spins through different[specified] states and back to the normal [accepting state]. This machine can be used to manipulate computer programs[talk about serialization and logical expressions], which require hardware and software manifestations.
The finite state machine[FSM] is never complete without the recall of its Computer science origin under the topic of 'Automata theory'. Automata[as plural], automaton in singular, in the light we can call the FSM, Finite State Automata-FSA [which I prefer].
Remember I talked about Turing completeness in my Ethereum Virtual Machine article, which pointed out how the EVM is Turing complete, and if a machine is 'Turing complete' it is said to perform all types of computational manipulations, which arguably makes it an infinite state machine. On the other hand, every other state machine that does not solve all computational problems is said to be Turing incomplete.
NB Turing machine > FSM.
Generally, the finite state machine is capable of receiving an action [instruction] that will lead to a change in the state.
Types of FSA
There are two types of Finite state automata namely;
- Determinitic Finite Automata [DFA]
- Non-Deterministic Finite Automata [NDFA or NFA]
DFA
Oh yeah, it can also be called a Deterministic Finite Acceptor, which takes defined strings of symbols that determine if the Finite machine rejects or accepts, hence running through the sequence of strings and giving out exactly what the symbol of the finite machine states.
The DFA is defined by a 5-tuple element; Q, ∑, δ, q0, F all with a unique definition. Wanna know more follow here. Remember mortal combats yeah, '>><<Z' [forward forward back back z]? haha, now this combination satisfies the state[brutality] in the DFA of a particular character, hence when completed will execute the action behind it. Chin chang ;-)
This image displays deterministic finite automation that accepts only the alphabet[a,b,c,d] with of multiple of 4, having the initial state S1, and S4 as accept state. This means that the string "abaac" leads to the state sequence S1, S2, S1, S2, S2, S4 and is hence accepted.
NDFA
Unlike the DFA this can move to any combination in the machine sequence without having any strict bounds as to happen or not, this means that it can have more than a transition function. It accepts input strings provided that it has a compatible space matching the string in the final[accept] state.
Now, this diagram can accept all combinations that will lead to it ending on the acceptance state, hence number combinations like [0, 1, 101, 1001...] are welcomed cause they end at the accept state of 'd'. And also combinations like [1, 01, 10, 0110...] cannot be accepted obviously. This is actually termed better cause it actually saves time, accepts null values, and does not take too many state and transitions to complete execution.
Application of FSA
Light Switch
State: On or Off Transition: The state 'on' changes when the state 'off' is applied
Elevator
State: Static, Dynamic Transition: When the floor number is pressed it changes from the static state to its dynamic state hence taking the user to the desired floor and back to the static state.
ATM Machine
State: Dispense, Static, Sing... Transition: The machine changes its state if conditions for withdrawing are 1k met from static to dispense or sing some motivational songs to a broke user.
Conclution
The state machine act as a wardrobe in that you keep your party, burial, and dating clothes, and when the mood is triggered according to your outfit you go ahead and put them on, hence changing the state of your dressing.
Never will I go without saying thank you for scrolling to the end, I know a lot people are waiting for you to share this so they can scroll to the end and give thumbs up too, and might even say something we want.
Macho Garcias!