SHRI VAISHNAV VIDYAPEETH
VISHAWAVIDYALAYA
SHRI VAISHNAV INSTITUTE OF INFORMATION TECHNOLOGY
Department of Computer Science and Engineering
Course Name : Formal
Language And Automata
Theory
Course Code:- BTCSCS201
II YEAR III SEM
SECTION – J-(TCS)
Submitted To:- Submitted By:-
Prof. Sunil Parihar Avadhi Jain
21100BTCSBS09682
INDEX
S. Date of Date of
N Experim Experiment Name Submissi Signature
o. ent on
Design a program for creating a machine that accepts strings
1.
having at least one zero.
Design a program for creating a machine that accepts strings
2.
having three consecutive zeroes.
3. Design a program for mod 3 machine(binary).
Design a program for creating a machine that accepts decimal
4.
number divisible by 3.
Design a program for creating a machine that accept all the
5.
strings ending with 101.
6. Design a program to convert NFA into DFA.
Design a program which counts number of zeroes and ones in a
7.
given string.
Design a program for PDA that accepts equal number of zeroes
8.
and ones at any place.
Design a program to create a PDA that accept the well formed
9.
parentheses.
Design a program to create a PDA that accepts wcwR where w
10
is string and wR is reverse of that string and C is constant.
Design a Turing Machine that accepts the following language :
11
L = {anbncn | n ≥ 1}
Experiment 1
Aim :
Design a program for creating a machine that accepts strings having at least one
zero.
Source Code :
/* C program to design a DFA which accepts all strings over alphabet 0,1
having at least one zero*/
#include <stdio.h>
#include <stdlib.h>
int main()
{
char str[100],s='A';
int i;
printf("Enter a valid string to be checked over alphabet {0,1} : ");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
switch(s)
{
case 'A':
if(str[i]=='0')
s='B';
else if(str[i]=='1')
s='A';
break;
case 'B':
if(str[i]=='0')
s='B';
else if(str[i]=='1')
s='B';
break;
}
}
if(s=='B')
printf("\nString is accepted", s);
else
printf("\nString is not accepted", s);
return 0;
}
Inputs :
Output of the source code :
Experiment 2
Aim :
Design a program for creating a machine that accepts strings having three
consecutive zeroes.
Source Code :
/* C program to design a DFA which accepts all strings over alphabet 0,1
that contains 3 consecutive zeroes */
#include <stdio.h>
#include <stdlib.h>
int main()
{
char str[100],s='A';
int i;
printf("Enter a valid string to be checked over alphabet {0,1} : ");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
switch(s)
{
case 'A':
if(str[i]=='0')
s='B';
else if(str[i]=='1')
s='A';
break;
case 'B':
if(str[i]=='0')
s='C';
else if(str[i]=='1')
s='A';
break;
case 'C':
if(str[i]=='0')
s='D';
else if(str[i]=='1')
s='A';
break;
case 'D':
if(str[i]=='0')
s='D';
else if(str[i]=='1')
s='D';
break;
}
}
if(s=='D')
printf("\nString is accepted", s);
else
printf("\nString is not accepted", s);
return 0;
}
Inputs :
Output of the source code :
Experiment 3
Aim :
Design a program for mod 3 machine(binary).
Source Code :
/* C program to design a program for mod 3 machine(binary) */
#include <stdio.h>
#include <stdlib.h>
int main()
{
char str[100],s='A';
int i;
printf("Enter a valid string to be checked over alphabet {0,1} : ");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
switch(s)
{
case 'A':
if(str[i]=='0')
s='A';
else if(str[i]=='1')
s='B';
break;
case 'B':
if(str[i]=='0')
s='C';
else if(str[i]=='1')
s='A';
break;
case 'C':
if(str[i]=='0')
s='B';
else if(str[i]=='1')
s='C';
break;
}
}
if(s=='A')
printf("\nString is divisible by 3\n", s);
else
printf("\nString is not divisble by 3\n", s);
return 0;
}
Inputs :
Output of the source code :
Experiment 4
Aim :
Design a program for creating a machine that accepts decimal number divisible by
3.
Source Code :
/* C program to design a program for creating a machine that accepts decimal number divisible
by 3.*/
#include<stdio.h>
int main()
{
char str[50],s='A';
int i;
printf("Enter a valid string :");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
switch(s)
{
case 'A':
if(str[i]=='0' || str[i]=='3' || str[i]=='6' || str[i]=='9')
s='A';
else if(str[i]=='1' || str[i]=='4' || str[i]=='7')
s='B';
else if(str[i]=='2' || str[i]=='5' || str[i]=='8')
s='C';
break;
case 'B':
if(str[i]=='0' || str[i]=='3' || str[i]=='6' || str[i]=='9')
s='B';
else if(str[i]=='1' || str[i]=='4' || str[i]=='7')
s='C';
else if(str[i]=='2' || str[i]=='5' || str[i]=='8')
s='A';
break;
case 'C':
if(str[i]=='0' || str[i]=='3' || str[i]=='6' || str[i]=='9')
s='C';
else if(str[i]=='1' || str[i]=='4' || str[i]=='7')
s='A';
else if(str[i]=='2' || str[i]=='5' || str[i]=='8')
s='B';
break;
}
}
if(s=='A')
printf("\nString is divisible by 3\n", s);
else
printf("\nString is not divisible by 3\n", s);
return 0;
}
Inputs :
Output of the source code :
Experiment 5
Aim :
Design a program for creating a machine that accept all the strings ending with 101.
Source Code :
/* C program to design a DFA which accepts all strings over alphabet 0,1
ending with 101 */
#include <stdio.h>
#include <stdlib.h>
int main()
{
char str[100],s='A';
int i;
printf("Enter a valid string to be checked over alphabet {0,1} : ");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
switch(s)
{
case 'A':
if(str[i]=='0')
s='A';
else if(str[i]=='1')
s='B';
break;
case 'B':
if(str[i]=='0')
s='C';
else if(str[i]=='1')
s='B';
break;
case 'C':
if(str[i]=='0')
s='A';
else if(str[i]=='1')
s='D';
break;
case 'D':
if(str[i]=='0')
s='C';
else if(str[i]=='1')
s='B';
break;
}
}
if(s=='D')
printf("\nString is accepted", s);
else
printf("\nString is not accepted", s);
return 0;
}
Inputs :
Output of the source code :
Experiment 6
Aim :
Design a program to convert NFA into DFA.
Source Code :
/* 1. If your states are q0, q1, q2 they will be represented as follows (in the table)
q0 = 2^0 = 1
q1 = 2^1 = 2
q2 = 2^2 = 4
2. Similarly union of states will be represented as -
q0,q1 = 2^0 + 2^1 = 3
q1, q2 = 2^1 + 2^2 = 6
q0,q1,q2 = 2^0 + 2^1 + 2^2 = 7*/
#include<stdio.h>
#include<string.h>
#include<math.h>
int ninputs;
int dfa[100][2][100] = {0};
int state[10000] = {0};
char ch[10], str[1000];
int go[10000][2] = {0};
int arr[10000] = {0};
int main()
{
int st, fin, in;
int f[10];
int i,j=3,s=0,final=0,flag=0,curr1,curr2,k,l;
int c;
printf("\nFollow the one based indexing\n");
printf("\nEnter the number of states::");
scanf("%d",&st);
printf("\nGive state numbers from 0 to %d",st-1);
for(i=0;i<st;i++)
state[(int)(pow(2,i))] = 1;
printf("\nEnter number of final states\t");
scanf("%d",&fin);
printf("\nEnter final states::");
for(i=0;i<fin;i++)
{
scanf("%d",&f[i]);
}
int p,q,r,rel;
printf("\nEnter the number of rules according to NFA::");
scanf("%d",&rel);
printf("\n\nDefine transition rule as \"initial state input symbol final state\"\n");
for(i=0; i<rel; i++)
{
scanf("%d%d%d",&p,&q,&r);
if (q==0)
dfa[p][0][r] = 1;
else
dfa[p][1][r] = 1;
}
printf("\nEnter initial state::");
scanf("%d",&in);
in = pow(2,in);
i=0;
printf("\nSolving according to DFA");
int x=0;
for(i=0;i<st;i++)
{
for(j=0;j<2;j++)
{
int stf=0;
for(k=0;k<st;k++)
{
if(dfa[i][j][k]==1)
stf = stf + pow(2,k);
}
go[(int)(pow(2,i))][j] = stf;
printf("%d-%d-->%d\n",(int)(pow(2,i)),j,stf);
if(state[stf]==0)
arr[x++] = stf;
state[stf] = 1;
}
//for new states
for(i=0;i<x;i++)
{
printf("for %d ---- ",arr[x]);
for(j=0;j<2;j++)
{
int new=0;
for(k=0;k<st;k++)
{
if(arr[i] & (1<<k))
{
int h = pow(2,k);
if(new==0)
new = go[h][j];
new = new | (go[h][j]);
}
}
if(state[new]==0)
{
arr[x++] = new;
state[new] = 1;
}
}
}
printf("\nThe total number of distinct states are::\n");
printf("STATE 0 1\n");
for(i=0;i<10000;i++)
{
if(state[i]==1)
{
//printf("%d**",i);
int y=0;
if(i==0)
printf("q0 ");
else
for(j=0;j<st;j++)
{
int x = 1<<j;
if(x&i)
{
printf("q%d ",j);
y = y+pow(2,j);
//printf("y=%d ",y);
}
}
//printf("%d",y);
printf(" %d %d",go[y][0],go[y][1]);
printf("\n");
}
}
return 0;
}
NFA
DFA for the above NFA
Output of the source code :
Experiment 7
Aim :
Design a program which counts number of zeroes and ones in a given string.
Source Code :
/* C program to design a program which counts number of zeroes and ones in a given string.
*/
#include<stdio.h>
int main()
{
char str[50],c1=0,c2=0;
int i;
printf("Enter a valid string :");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
if(str[i]=='0')
{
c1=c1+1;
}
else if(str[i]=='1')
{
c2=c2+1;
}
}
printf("\nThe number of zeroes is %d",c1);
printf("\nThe number of ones is %d",c2);
return 0;
}
Output of the Source code :
Experiment 8
Aim :
Design a program for PDA that accepts equal number of zeroes and ones at any
place.
Source Code :
/* C++ program design a program for PDA that accepts equal number of zeroes and ones at any place.*/
#include<iostream>
#include<string.h>
using namespace std;
int top;
char s[10];
class Stack
{
public:
void push(int x)
{
s[top++]=x;
}
void pop(int x)
{
s[top--]=x;
}
};
int main()
{
int i,n;
char a[10];
cout<<"Enter String over alphabet {0,1} : ";
cin>>a;
n=strlen(a);
Stack st;
top=-1;
if(a[0]=='0')
{
for(i=0;i<n;i++)
{
if(a[i]=='0')
{
st.push(a[i]);
}
else
{
st.pop(a[i]);
}
}
}
if(a[0]=='1')
{
for(i=0;i<n;i++)
{
if(a[i]=='1')
{
st.push(a[i]);
}
else
{
st.pop(a[i]);
}
}
}
if(top==-1)
{
cout<<"\nString Accepted.\n";
}
else
{
cout<<"\nString Rejected.\n";
}
return 0;
}
Inputs :
Output of the source code :
Experiment 9
Aim :
Design a program to create a PDA that accept the well formed parentheses.
Source Code :
/* C++ program to design a program to create a PDA that accept the well formed parentheses.*/
#include<iostream>
#include<string.h>
using namespace std;
int top;
char s[10];
class Stack
{
public:
void push(int x)
{
s[top++]=x;
}
void pop(int x)
{
s[top--]=x;
}
};
int main()
{
int i,n;
char a[10];
cout<<"Enter String over alphabet {(,)} : ";
cin>>a;
n=strlen(a);
Stack st;
top=-1;
if(a[0]=='(')
{
for(i=0;i<n;i++)
{
if(a[i]=='(')
{
st.push(a[i]);
}
else
{
st.pop(a[i]);
}
}
}
else
{
goto E;
}
if(top==-1)
{
cout<<"\nString Accepted.\n";
}
else
{
E:
cout<<"\nString Rejected.\n";
}
return 0;
}
Inputs :
Output of the source code :
Experiment 10
Aim :
Design a program to create a PDA that accepts wcwR where w is string and wR is
reverse of that string and C is constant.
Source Code :
/* C++ program to design a program to create a PDA that accepts wcwR where w is string and
wR is reverse of that string and C is constant.*/
#include<iostream>
#include<string.h>
using namespace std;
int top;
char s[10];
class Stack
{
public:
void push(int x)
{
s[top++]=x;
}
void pop(int x)
{
s[top--]=x;
}
};
int main()
{
int i,n,state=0;
char a[10];
cout<<"Enter a string over alphabet {a,b} : ";
cin>>a;
n=strlen(a);
Stack st;
top=-1;
for(i=0;i<n;i++)
{
if(a[i]=='a' && state==0)
{
st.push(a[i]);
state=0;
}
else if(a[i]=='b' && state==0)
{
st.push(a[i]);
state=0;
}
else if(a[i]=='c' && state==0)
{
state=1;
}
else if(a[i]=='a' && state==1)
{
st.pop(a[i]);
state=1;
}
else if(a[i]=='b' && state==1)
{
st.pop(a[i]);
state=1;
}
else
{
break;
}
}
if(a[i]=='\0' && top==-1 && state==1)
{
state=100;
}
if(state==100)
{
cout<<"String Accepted."<<endl;
}
else
cout<<"String Rejected."<<endl;
return 0;
}
Inputs :
Output of the Source code :
Experiment 11
Aim :
Design a Turing Machine that accepts the following language :
L = {a^n b^n c^n | n ≥ 1}
Source Code :
# Python program to design a Turing Machine that accepts the following language :
L = {a^n b^n c^n | n ≥ 1}.*/
def action(input_char, replace_with, move, new_state):
global tapehead, state
if tape[tapehead] == input_char:
tape[tapehead] = replace_with
state = new_state
if move == 'L':
tapehead -= 1
else:
tapehead += 1
return True
return False
string = input("Enter String: ")
length = len(string) + 2
tape = ['B']*length
i = 1
tapehead = 1
for s in string: #loop to place string in tape
tape[i] = s
i += 1
state = 0
#assigning characters to variable so that don't have to use characters each time
a, b,c, X, Y,Z, R, L, B = 'a', 'b','c', 'X', 'Y','Z' , 'R', 'L', 'B'
oldtapehead = -1
accept = False
while(oldtapehead != tapehead): #if tapehead not moving that means terminate Turing m
achine
oldtapehead = tapehead
print(tape , "with tapehead at index", tapehead, "on state" , state)
if state == 0:
if action(a, X, R, 1) or action(Y, Y, R, 4):
pass
elif state == 1:
if action(a, a, R, 1) or action(Y, Y, R, 1) or action(b, Y, R, 2):
pass
elif state == 2:
if action(Z, Z, R, 2) or action(b, b, R, 2) or action(c, Z, L, 3):
pass
elif state == 3:
if action(b, b, L, 3) or action(Z, Z, L, 3) or action(a, a, L, 3) or action(Y
,Y,L,3) or action(X, X, R, 0) :
pass
elif state == 4:
if action(Y, Y, R, 4) or action(Z, Z, R, 5) :
pass
elif state == 5:
if action(Z, Z, R, 5) or action(B,B,R,6):
pass
else:
accept = True
if accept:
print("String accepted on state = ", state)
else:
print("String not accepted on state = ", state)
Inputs :
Output of the source code :
