Practical - 01
AIM: Design a Finite State Machine (FSM) that accepts all strings over input symbols {0, 1} having three consecutive 1's as a substring.
Discussion:
As per the AIM, set of valid strings are represented by set A:
A = {111, 0111, 1110, 0101011110101,...}
means any string should be declared valid if it contains 111 as a substring.
Let M be the machine for above AIM, hence it can be define as M(Q, Σ, 𝛿, q0, F)
where
Q: set of states: {A, B, C, D}
Σ: set of input symbols: {0, 1}
q0: initial state (A)
F: set of Final states: {D}
𝛿: Transition Function: (Transition state diagram is shown in Figure 1.)
| - | ||
| A | A | B |
| B | A | C |
| C | A | D |
| D | D | D |
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 of 0 and 1)\n";
gets(Input);
int i=-1;
A:
i++;
if(Input[i]=='0')
{
goto A;
}
else if(Input[i]=='1')
{
goto B;
}
else if(Input[i]=='\0')
{
goto Invalid;
}
else
{
goto Wrong;
}
B:
i++;
if(Input[i]=='0')
{
goto A;
}
else if(Input[i]=='1')
{
goto C;
}
else if(Input[i]=='\0')
{
goto Invalid;
}
else
{
goto Wrong;
}
C:
i++;
if(Input[i]=='0')
{
goto A;
}
else if(Input[i]=='1')
{
goto D;
}
else if(Input[i]=='\0')
{
goto Invalid;
}
else
{
goto Wrong;
}
D:
i++;
if(Input[i]=='0')
{
goto D;
}
else if(Input[i]=='1')
{
goto D;
}
else if(Input[i]=='\0')
{
goto Valid;
}
else
{
goto Wrong;
}
Valid:
cout<<"\n Output: Valid String";
goto exit;
Invalid:
cout<<"\n Output: Invalid String";
goto exit;
Wrong:
cout<<"\n Please enter binary string {format of 0, 1}";
exit:
getch();
}
