# FINITE STATE MACHINE (FSM)

Tutorial by
Mepits

Sections

## FINITE STATE MACHINE (FSM)

We all know that different systems behave differently in various conditions. Finite State Machine (FSM) is an easy technique used to model the behaviour of a system in various conditions. The function of a Finite State Machine is to detect the particular behavioural pattern of the system when it is subjected to various conditions. Let’s call this Finite State Machine as an FSM simply. Now the next thing is how the FSM models the behaviour of a system. That is the main content in this tutorial.

Have you heard about ‘state’? I am asking this question because of a specific reason. That is, ‘state’ and ‘state transition’ are the two important things that you should learn before learning FSM. Because FSM models the behaviour of a system by representing it in different states it can be in and the transition between each state.

A state is simply a specific action. Example for action is waiting for button 1 is to be pressed, or rotating the dc motor to any direction etc. So, what I am trying to explain is FSM is a computer program that, at any point in time, can be in one of a predetermined number of states. The first thing before creating an FSM model is to learn the particular behavioural pattern of a system. We can explain that with the help of an example. In order to get the basic concepts of FSM, we can start with an example of a simple sequence detector.

FSM can be created in two ways. By using Mealy machine and Moore machine. In the Mealy machine, the output of the system depends on the present state and the present input also. But in the case of Moore machine, the output of the system depends on the present state only.

Mealy Machine

If the output of the system depends not only on the present state but also on the present input, we can call this system as a Mealy machine. If you are a beginner in FSM, I am sure that you will not be satisfied by this definition. So I will explain Mealy machine with an example of a sequence detector.

Let’s consider a sequence 1101. If we want to generate this sequence, the first thing that we do is to find the possible states. In order to get 1101 sequence, we can divide the whole process into four steps.

Step 1

Consider, initially the system is in state S0. From the given sequence, it is clear that in the first state what we want is 1 (because our sequence is 1101). So initially the system is in state S0 and to get 1 we will just provide an input 1. Whenever input 1 is given, the system moves to state S1. Refer fig.1. Here, initially, the system is in state S0. If we provide an input 0, the system will remain in state S0 itself. If we provide an input 1, the system will go to state S1.

Fig.1: If the present input is 1 or 0 in State 0

The reason for providing 1/0 in fig.1 is that we are providing an input 1 and the output is 0.

I think you got confused now. Only when we get the last output (1101), we give as 1/1. What do you understand from this? If we notice that any 1/1 or 0/1 in a state diagram, just recall that, that would be the last state of that state machine.

Step 2

The next state we want is 11 (ie, 1101). So we provide an input 1 so that it can go to state S2.

Fig.2: If the present input is 1 in State 1

Also, you should check what if the input is 0 from S1. If the input is 0, we should start the state machine again in this case. So, again the system goes to state S0. Refer Fig 3.

Fig.3: If the present input is 0 in state 1

Step 3

The next input we want is 0 (1101). We already have 11 at S2. To get 110, we provide an input 0 so that it can move to state S3. So to reach S3 the sequence 110 should be given.

Fig.4: If the present input is 0 in state 2

We should also check the input 1 condition in state S2. We already checked what if the input from S2 is 0. Next, we should check what if the input from S2 is 1. If input from S2 is 1, it should remain in that state itself.

Let me explain. We want a sequence 1101. At S2 we got up to 11 of the 1101 sequence. Next, we want to check whether the next input is 1 or 0. More specifically, we want to check whether 111 or 110. If 110, it will go to next state S3 that I mentioned in the earlier case. If input at s2 state is 1(we will get 111), we select the last 11 of 111. Because the next digit may be 0, what we exactly wanted. So, the state diagram will remain in S2 itself, to detect 11. Refer fig.5.

Fig.5: If the present input is 1 in state 2

Step 4

By the next transition, we will get the output sequence. The next state we want is 1101 (1101). We already have 110 at our state S3. To get the last digit in our sequence, remember that digit is 1, we can go back to the particular state whose outcome is 1. That’s exactly state S1. And remember one thing. This is the output state. So don’t forget to write 1/1. Refer Fig.6.

Fig.6: If the present input is 1 in state 3

Also, we want to check the zero condition of state S3. That is, if we have 1101 (mentioned in the earlier case), we will go to state S1. But if we have 1100, we will go to state S0 to start the state machine again. Refer Fig.7.

Fig.7: FSM Model of 1101 sequence

The program in MPLAB regarding the 1101 sequence detector is provided below.

```#include <stdio.h>

#include <stdlib.h>

#define _XTAL_FREQ 4000000

// PIC16F877A Configuration Bit Settings

// 'C' source line config statements

#include <xc.h>

// #pragma config statements should precede project file includes.

// Use project enums instead of #define for ON and OFF.

// CONFIG

#pragma config FOSC = HS

#pragma config WDTE = OFF

#pragma config PWRTE = OFF

#pragma config BOREN = ON

#pragma config LVP = OFF

#pragma config CPD = OFF

#pragma config WRT = OFF

#pragma config CP = OFF

char rx();

void tx(unsigned char);

void string(char *);

int count=0;

void main()

{

int input=0;

int state=0;

char s[20];

TXSTA=0X24;

RCSTA=0X90;

SPBRG=25;

TRISC=0X80;

string("WELCOME\n\r");

string("GIVE THE PATTERN\n\r");

while(1)

{

input=rx();

tx(input);

switch (state)

{

case 0:

if(input=='0')

state=0;

else

state=1;

break;

case 1:

if(input=='0')

state=0;

else

state=2;

break;

case 2:

if(input=='0')

state=3;

else

state=2;

break;

case 3:

if(input=='0')

state=0;

else

{

state=1;

string("\n\rMATCH FOUND:::::1101\n\r");

count++;

sprintf(s,"PATTERN COUNTED= %d\n\r",count);

string(s);

state=0;

string("CONTINUE GIVING PATTERN\n\r");

}

break;

}

}

}

void tx(unsigned char a)

{

TXREG=a;

while(!TRMT);

}

void string(char *p)

{

int i;

for(i=0;*(p+i)!='\0';i++)

{

tx(*(p+i));

}

}

char rx()

{

while(!RCIF);

return RCREG;

}```

Simulation diagram in proteus and the output regarding that is provided in Fig.8 and Fig.9 respectively.

Fig.8: Simulation diagram in proteus

Fig.9: Output of the 1101 pattern detector

User Review (24)

#### Rank Xone

The column is typically a vertical vessel filled with a packing material, such as glass beads, metal or plastic rings, or other materials that provide a large surface area for liquid-vapor contact. packed bed reactor

Reply  Report Abuse   17 March,2023 03:03

#### Jacket Hunt

love the content of this blog and the positive intent you have. Thanks! western leather jacket

Reply  Report Abuse   08 March,2023 12:03

#### astuc tuc

I have been looking for articles on these topics for a long time. safetoto I don't know how grateful you are for posting on this topic. Thank you for the numerous articles on this site, I will subscribe to those links in my bookmarks and visit them often. Have a nice day

Reply  Report Abuse   16 February,2023 09:02

#### Telesa Rose

[https://domain Key1] [[https://domain|Key2]] [Key3](https://domain) [Key4]: https://domain Key5 [url=https://domain]Key6[/url] “Key7": https://domain [link= https://domain url]Key8[/link]

Reply  Report Abuse   15 February,2023 02:02

#### Telesa Rose

[https://domain Key1] [[https://domain|Key2]] [Key3](https://domain) [Key4]: https://domain Key5 [url=https://domain]Key6[/url] “Key7": https://domain [link= https://domain url]Key8[/link]

Reply  Report Abuse   15 February,2023 02:02

#### topboosterseo TopBoosterSEO

Great tips! I will try to use them. A hard-hitting post. Prodentim

Reply  Report Abuse   13 February,2023 11:02

#### safetycasino safetycasino

There must have been many difficulties in providing this information. totosafe Nevertheless, thank you for providing such high-quality information.

Reply  Report Abuse   01 February,2023 12:02

#### wang xiao

Do you want to be the one to find the most correct answer in wordle game? ???? ??????

Reply  Report Abuse   08 December,2022 09:12

#### wang xiao

Do you want to be the one to find the most correct answer in wordle game? Start learning about this game at our [url=https://twbaojian.com/goods.php?id=37]???[/url] [url=https://twbaojian.com/goods.php?id=40]????[/url] [url=https://twbaojian.com/goods.php?id=41]????[/url]

Reply  Report Abuse   08 December,2022 09:12

#### Patsy Moore

We'll make sure this list is kept up to date because strongest character in dragon ball legends routinely receives upgrades and balancing adjustments. It's also important to remember that even the most powerful personalities can suffer in the absence of a strong team supporting them. We advise you to visit our Genshin Impact tier list, Super Smash Bros., for more material similar to this. It's easy to tell the review early on how Live A Live's remake by Square Enix influenced Chrono Trigger. Director Takashi Tokita obviously utilized 1994's Live A Live as a springboard for his ultimate masterwork, from spanning numerous timeframes to the unique area of effect talents and right down to the simple, sometimes complex story.

Reply  Report Abuse   26 August,2022 06:08

#### jack kiwab

Quickly this site might undoubtedly become well-known among most blogging and site-building people, for that painstaking posts as well as critiques. Imlie Today Episode

Reply  Report Abuse   10 August,2022 03:08

#### jack kiwab

I discovered your website web site on the search engines and appearance a couple of your early posts. Always keep the excellent operate. I merely extra increase Rss to my MSN News Reader. Seeking forward to reading more from you down the road!… ??? 2?

Reply  Report Abuse   09 August,2022 02:08

I have express a few of the articles on your website now, and I really like your style of blogging. I added it to my favorite’s blog site list and will be checking back soon… Lead generation

Reply  Report Abuse   02 July,2022 04:07

You might comment on the order system of the blog. You should chat it's splendid. Your blog audit would swell up your visitors. I was very pleased to find this site.I wanted to thank you for this great read!! Lead generation

Reply  Report Abuse   02 July,2022 04:07

Great post I would like to thank you for the efforts you have made in writing this interesting and knowledgeable article. Lead generation

Reply  Report Abuse   02 July,2022 04:07

it's really cool blog. Linking is very useful thing.you have really helped Lead generation

Reply  Report Abuse   02 July,2022 04:07

I would like to say that this blog really convinced me to do it! Thanks, very good post. Lead generation

Reply  Report Abuse   02 July,2022 03:07

You know your projects stand out of the herd. There is something special about them. It seems to me all of them are really brilliant! Lead generation

Reply  Report Abuse   02 July,2022 03:07

#### Bilal Hassan

Reply  Report Abuse   29 May,2022 04:05

#### amyu suka

Thank you for sharing this great post, I am very impressed with your post, the information given is detailed and easy to understand. I will follow your next post often. crossword puzzles

Reply  Report Abuse   11 May,2022 01:05

#### dimaria bend

I enjoyed reading your essay and look forward to reading more of it in the future. If you have any spare time, I recently discovered a terrific game called five nights at freddy's which you are welcome to join and play with me if you so like.

Reply  Report Abuse   24 December,2021 06:12