Computer Science is a vast subject and the technology it offers is advancing rapidly, benefiting us in numerous ways. While Quantum Computers is a very hot topic, but what I'm going to discuss today is something old and basic.
As you know Artificial Intelligence is very common nowadays. Electronic gadgets, applications, games and what not is based on it. These applications exhibit intelligence, like a human brain works, if given different scenarios.
Have you ever wondered how does these apps work? For instance, if you talk about games, there are plenty of scenarios, a user could get into. Now, if you are a programmer, if-else statements must have come into your mind.
if(Mario hits a brick and coins pop)
{Add Coins}
else if (Mario hits a brick and flower pops)
{Grow Mario}
else if (Mario falls or hits a bug)
{GAME OVER}I have just typed three possibilities, whereas there could be plenty. Imagine writing hundreds of if-else or switch statements.
Here comes Finite State Machine into the picture which is hypothetical, of course. But it helps in writing the code and also minimize the spaghetti code. It is widely used by game developers.
It's very informal FSM (Finite State Machine). I just want to give you a picture of where are we going.
In early 20th century, hypothetical models of neural networks and states were designed. This study formed the basis of Automata Theory. Automata is plural, Singular is Automaton which means self-acting.
Now if you google Automata Theory, you will find out that it's been classified into layers.
So the basic concept that I want to discuss is Finite State Machine.
It’s an abstract machine which has finite states at any given time. According to the input received, states change. There is an initial state and final state and the states in between as required. Any current state has no information of the previous state thus it has no memory.
There are many practical examples of FSM like elevators, vending machines, combination locks, traffic lights, games. I will explain to you with the help of state diagrams for your better understanding.
Above is some game where you have to go to Start state and just move along according to the arrows.
_______________________
In this diagram there are three possible states of a LED switch i.e., IDLE, ON, OFF.
At first, machine is in IDLE state. It receives an input 1, then it makes transition to ON state.
Now at ON state, machine receives an input 0, it makes transition to OFF.
Here is a little transition table I have made. This kind of notation comes handy while programming.
| Current State | Input | Next State |
|---|---|---|
| Idle | Start/1 | On |
| On | Toggle/0 | Off |
| Off | Toggle/1 | On |
_________________________
Now in this image you can see we are trying to detect sequence 1011. I have drawn a transition table for this state diagram as well.
| Current State | Input | Next State |
|---|---|---|
| S0 | 0-1 | S0-S1 |
| S1 | 0-1 | S2-S1 |
| S2 | 0-1 | S0-S3 |
| S3 | 0-1 | S2-S1 |
___________________________
There are several types of Finite State Machines:
Acceptors produce binary output i,e accepted or rejected. Here is an example.
Here I tried to pattern-match of the string STEEMIT.
_______________________
Sequence Detector or Recognizers are also basically type of Acceptors.
Transducers
These are not like FSM. While FSM can do pattern-matching, it can parse the string. It's widely used in Natural Langugae Processing.
It has two tapes, can read from one tape and write to another tape. So basically it has memory.
Classifiers
These are like Acceptors but have single ouput and two termintation states.
Deterministic have no or single transition from every state. While non-deterministic can have multiple.
Those of you who are thinking that I'm making a useless fuss and making flow charts, must know that:
Finite State Machines are not Flow Charts.
I will tell you the difference. First, there are no states in flow charts. Those are Stages. And those stages don't require a certain input to move onto next stage. They move automatically on completion.
I have explained the basics of FSM, there is more to it. As you can see I haven't explained some types in detail. I have left that on purpose. We will discuss it in later posts.
I ask you a question:
Personal Computers are FSM or TM (Turing Machine) based?
I haven't discussed Turing Machine yet. It's an infinite tape and has memory, in short.
I read somewhere, Modeling Infinity is not the same as Obtaining Infinity.
So that could make our computers FSM based. But there is no computation successfully performed by Turing Machine that cannot be performed by our computers. So this makes it TM based too.
We know that Turing Machine is way more powerful than FSM because FSM can easily fall on a non-ending state or can catch up on a loop hole and it has no memory.
There are practical limitations but still computers can run any Turing program.
FSM and TM both helped us a lot in developing different programs.
1 - https://en.wikipedia.org/wiki/Finite-state_machine
2 - https://www.reddit.com/r/learnpython/comments/1z4jjk/finite_state_machines/
3- http://www.programmingbasics.org/en/beginner/fsm.html