Practical - 03
AIM: Design a Finite State Machine (FSM) that accepts all decimal string which are divisible by 3.
Discussion:
As per the AIM, set of valid strings are represented by set A:
A = {0, 3, 6, 9, 03, 06, 09, 12, 012, ..}
means any decimal number string that when divided by three gives remainder zero.
Let M be the machine for above AIM, hence it can be define as M(Q, Σ, 𝛿, q0, F)
where
Q: set of states: {q, q0, q1, q2}
Σ: set of input symbols: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
q0: initial state (q)
F: set of Final states: {q0}
𝛿: Transition Function: (Transition state diagram is shown in Figure 1.)
| - | |||
| q | q0 | q1 | q2 |
| q0 | q0 | q1 | q2 |
| q1 | q1 | q2 | q0 |
| q2 | q2 | q0 | q1 |
Code in C++
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
char Input[100];
clrscr();
cout<<"Enter a string to validate (input string should be decimal number (i.e constructed from 0,1,2,3,4,5,6,7,8,9 digits)\n";
gets(Input);
int i=-1;
q:
i++;
if(Input[i]=='0'|| Input[i]=='3'|| Input[i]=='6'|| Input[i]=='9')
{
goto q0;
}
else if(Input[i]=='1'|| Input[i]=='4'|| Input[i]=='7')
{
goto q1;
}
else if(Input[i]=='2'|| Input[i]=='5'|| Input[i]=='8')
{
goto q2;
}
else if(Input[i]=='\0')
{
goto Invalid;
}
else
{
goto Wrong;
}
q0:
i++;
if(Input[i]=='0'|| Input[i]=='3'|| Input[i]=='6'|| Input[i]=='9')
{
goto q0;
}
else if(Input[i]=='1'|| Input[i]=='4'|| Input[i]=='7')
{
goto q1;
}
else if(Input[i]=='2'|| Input[i]=='5'|| Input[i]=='8')
{
goto q2;
}
else if(Input[i]=='\0')
{
goto Valid;
}
else
{
goto Wrong;
}
q1:
i++;
if(Input[i]=='0'|| Input[i]=='3'|| Input[i]=='6'|| Input[i]=='9')
{
goto q1;
}
else if(Input[i]=='1'|| Input[i]=='4'|| Input[i]=='7')
{
goto q2;
}
else if(Input[i]=='2'|| Input[i]=='5'|| Input[i]=='8')
{
goto q0;
}
else if(Input[i]=='\0')
{
goto Invalid;
}
else
{
goto Wrong;
}
q2:
i++;
if(Input[i]=='0'|| Input[i]=='3'|| Input[i]=='6'|| Input[i]=='9')
{
goto q2;
}
else if(Input[i]=='1'|| Input[i]=='4'|| Input[i]=='7')
{
goto q0;
}
else if(Input[i]=='2'|| Input[i]=='5'|| Input[i]=='8')
{
goto q1;
}
else if(Input[i]=='\0')
{
goto Invalid;
}
else
{
goto Wrong;
}
Valid:
cout<<"\n Output: Valid String";
goto exit;
Invalid:
cout<<"\n Output: Invalid String";
goto exit;
Wrong:
cout<<"\n Please enter valid decimal number string";
exit:
getch();
}
