Design a Finite State Machine (FSM) that accepts all strings over input symbols {0, 1}
having three consecutive 1's as a substring.
Code:
#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();
}
Design a Finite State Machine (FSM) that accepts all decimal string which are divisible by 3.
#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();
}
Design a Push Down Automata (PDA) that accepts all string having equal number of 0's and 1's over input
symbol {0, 1} for a language 0n1n where n >= 1.
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
char Input[100];
char stack[100]; //Implementing stack through array.
int Top = -1;
clrscr();
cout<<"Enter binary string to validate (input string should be of 0 and 1)\n";
gets(Input);
stack[++Top] = 'Z';//Taking 'Z'as an initial stack symbol.
int i=-1;
q0:
i++;
if(Input[i]=='0' && stack[Top]== 'Z')
{ stack[++Top]= 'A';
goto q0; }
else if(Input[i]=='0' && stack[Top]== 'A')
{ stack[++Top]= 'A';
goto q0;}
else if(Input[i]=='1' && stack[Top]== 'A')
{ Top--;
goto q1; }
else { goto Invalid; }
q1:
i++;
if(Input[i]=='1' && stack[Top]== 'A')
{ Top--;
goto q1;}
else if(Input[i]=='\0' && stack[Top]== 'Z')
{ Top--;
goto q2; }
else { goto Invalid;}
q2:
cout<<"\n Output: Valid String";
goto exit;
Invalid:
cout<<"\n Output: Invalid String";
goto exit;
exit:
getch();
}
Design a PDA to accept WCWR where w is any binary string and WR is reverse of that string and C is a
special symbol.
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main() { char Input[100] , stack[100];
int Top = -1 , i=-1;
cout<<"Enter string to be validate\n";
gets(Input);
stack[++Top] = 'Z';//Taking 'Z'as an initial stack symbol.
q0: i++;
if(Input[i]=='0' && stack[Top]== 'Z')
{ stack[++Top]= 'A';
goto q0;}
else if(Input[i]=='1' && stack[Top]== 'Z')
{ stack[++Top]= 'B';
goto q0;}
else if(Input[i]=='0' && (stack[Top]== 'A'|| stack[Top]== 'B'))
{ stack[++Top]= 'A';
goto q0;}
else if(Input[i]=='1' && (stack[Top]== 'A'|| stack[Top]== 'B'))
{ stack[++Top]= 'B';
goto q0;}
else if(Input[i]=='C' && (stack[Top]== 'A'||stack[Top]== 'B'))
{ goto q1;}
else { goto Invalid; }
q1: i++;
if(Input[i]=='0' && stack[Top]== 'A')
{ Top--;
goto q1;}
else if(Input[i]=='1' && stack[Top]== 'B')
{ Top--;
goto q1;}
else if(Input[i]=='\0' && stack[Top]== 'Z')
{ goto Valid; }
else { goto Invalid;}
Valid: cout<<"\n Output: Valid String";
goto exit;
Invalid: cout<<"\n Output: Invalid String";
goto exit;
exit: getch();
}
Design a Turing Machine that calculates 2's complement of given binary string.
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
char Input[100];
cout<<"Enter input binary string\n";
gets(Input);
int i=0;
q0: if(Input[i]=='0'|| Input[i]=='1') { i++;
goto q0;}
else if(Input[i]=='\0'){ i--;
goto q1;}
else { goto Invalid; }
q1: if(Input[i]=='0') {i--;
goto q1; }
else if(Input[i]=='1') { i--;
goto q2;}
else { goto Invalid; }
q2: if(Input[i]=='0') {
Input[i]='1';
i--;
goto q2; }
else if(Input[i]=='1') { Input[i]='0';
i--;
goto q2;}
else if(i== -1) { goto q3; }
else { goto Invalid;}
q3: out<<"\nOutput: Two's complement is";
puts(Input);
goto exit;
Invalid: cout<<"\n You have entered some invalid string.";
goto exit;
exit: getch(); }
