Gyan Ganga College of Technology, Jabalpur

Department of Computer Science & Engineering

Branch: CS
Semester: V
Practical File
Theory of Computation [CS 501]

Student’s Name : _____________

Student’s Roll No: _ _ _ _ _ _ _ _ _ _ _ _ _

Faculty In-charge
Prof. Om Singh Parihar
[Department of CSE]

Session: 2021-22
Index
SN AIM DATE SIGN REMARK
1 Design a Program for creating machine
that accepts three consecutive zero

2 Design a Program for creating machine

that accepts the string always ending with
101.

3 Design a DFA which will

accept all the strings ending
with 00 over an alphabet {0,1}
and write a program to
implement the DFA.
4 Design a Program for Mode 2 Machine
5 Design a Program for Mode 3
Machine
6 Design a program for accepting decimal
number divisible by 2
7 Design a Program to find 2’s complement
of a given binary number.
8 Design a program for creating a machine
which accepts string having equal no. of
1’s and 0’s.
9 Design a program for creating a
machine which count number of 1’s
and 0’s in a given string.
10 Design a Program to find 1’s
complement of a given binary
number.

11 Design a Program which will

increment the given binary number by
1.

12 Design a Program to create PDA machine

that accept the well-formed parenthesis
13 Design a Push Down automata for
L={(0^n1^n| n>=1}
Aim1. Design a Program for creating machine that accepts three consecutive zero.

#include <stdio.h>

int main()
{
char str1[80], str2[80]="000";
int l, i, j;

printf("Enter Any string over input alphabets {0,1} : \n");

gets(str1);

//finding length of second string

for (l = 0; str2[l] != '\0'; l++);

for (i = 0, j = 0; str1[i] != '\0' && str2[j] != '\0'; i++)

{
if (str1[i] == str2[j])
{
j++;
}
else
{
j = 0;
}
}

if (j == l)
{
printf("String Accepted in Language ");
}
else
{
printf("String Rejected not in Language");
}

return 0;
}

OUTPUT: Enter Any string over input alphabets {0,1} :

INPUT:1001000
String Accepted in Language

INPUT:1001001
String Rejected not in Language
Aim2. Design a Program for creating machine that accepts the string always ending with 101.

#include <iostream>
#include<string.h>
using namespace std;
int main()
{ charstr[50];
inti,j, n;
charendstr[]="101";
cout<<"\nEnter a string over input alphabets {0,1}\n";
cin>>str;

n=strlen(str);

for(i=n-3,j=0;i<n,j<3;i++,j++)
{
if(endstr[j]==str[i] )
{

}
else
{
cout<<"String Rejected...";
exit(0);
}

if(j==3)
{
cout<<"String Accepted...";
exit(0);
}

return 0;
}

OUTPUT:
INPUT:1110101
String Accepted..

INPUT:11101011
String Rejected..
Aim3. Design a DFA which will accept all the strings ending with 00 over
an alphabet {0, 1} and write a program to implement the DFA.

#include <stdio.h>

#define max 100

main()

charstr[max],f='a';

inti;

printf("Enter Any string over input alphabets {0,1} : \n ");

scanf("%s",str);

for(i=0;str[i]!='\0';i++)

switch(f)

case 'a': if(str[i]=='0') f='b';

else if(str[i]=='1') f='a';

break;

case 'b': if(str[i]=='0') f='c';

else if(str[i]=='1') f='d';

break;

case 'c': if(str[i]=='0') f='c';

else if(str[i]=='1') f='d';

break;

case 'd': if(str[i]=='0') f='b';

else if(str[i]=='1') f='d';

break;

if(f=='c') printf("\nString is accepted as it reached the final state %c at the end.",f);

elseprintf("\nString is not accepted as it reached %c state which is not the final state.",f);

OUTPUT:

Enter Any string over input alphabets {0,1} :

INPUT:111100

String is accepted as it reached the final state c at the end

INPUT:1111001

OUTPUT: String is not accepted as it reached d state which is not the final state

Aim:4Design a DFA for |W| Mode 2=0 Machine over input alphabets {a,b}
#include <stdio.h>

#define max 100

main()

charstr[max],f='1';

inti;

printf("Enter Any string over input alphabets {a,b} : \n ");

scanf("%s",str);

for(i=0;str[i]!='\0';i++)

switch(f)

case '1': if(str[i]=='a' || str[i]=='b' ) f='2';

break;

case'2': if(str[i]=='a' || str[i]=='b') f='1';

break;

}
if(f=='1') printf("\nString is accepted as it reached the final state %c at the end.",f);

elseprintf("\nStringis not accepted as it reached STATE %c which is not the final state.",f);

OUTPUT:

Enter Any string over input alphabets {a,b} :

INPUT:abab

String is accepted as it reached the final state 1 at the end

INPUT:bab

OUTPUT: String is not accepted as it reached 2 state which is not the final state

Aim5.Design a DFA for |w| Mode 3=0 Machine over input alphabets {a,b}
#include <stdio.h>

#define max 100

main()

charstr[max],f='1';

inti;

printf("Enter Any string over input alphabets {a,b} : \n ");

scanf("%s",str);

for(i=0;str[i]!='\0';i++)

switch(f)

case '1': if(str[i]=='a' || str[i]=='b' ) f='2';

break;

case'2': if(str[i]=='a' || str[i]=='b') f='3';

break;

case '3': if(str[i]=='a' || str[i]=='b' ) f='1';

break;

}
}

if(f=='1') printf("\nString is accepted as it reached the final state %c at the end.",f);

elseprintf("\nString is not accepted as it reached %c state which is not the final state.",f);

OUTPUT:

Enter Any string over input alphabets {a,b} :

INPUT:aab

String is accepted as it reached the final state 1 at the end

INPUT:baba

OUTPUT: String is not accepted as it reached 2 state which is not the final state

Aim6.Design a program for accepting decimal number divisible by 2.

#include <iostream>
using namespace std;
int main() {
intdnum;
cout<<”enter any decimal no:”;
cin>>dnum;
if(dnum % 2 == 0)
cout<<num<<" is Divisible by 2";
else
cout<<num<<" is not Divisible by 2";
return 0;
}

OUTPUT:
enter any decimal no:12
12 is is Divisible by 2

enter any decimal no:15

15 is isnot Divisible by 2
Aim 7. Design a Program to find 2’s complement of a given binary number.
// Function to find two's complement
stringfindTwoscomplement(string str)
{
intn = str.length();

// Traverse the string to get first '1' from

// the last of string
inti;
for(i = n-1 ; i>= 0 ; i--)
if(str[i] == '1')
break;

// If there exists no '1' concatenate 1 at the

// starting of string
if(i == -1)
return'1'+ str;

// Continue traversal after the position of

// first '1'
for(intk = i-1 ; k >= 0; k--)
{
//Just flip the values
if(str[k] == '1')
str[k] = '0';
else
str[k] = '1';
}

// return the modified string

returnstr;;
}

// Driver code
intmain()
{
stringstr = "00000101";
cout<<“Two’s Complement :”findTwoscomplement(str);
return0;
}

OUTPUT:
INPUT:100100
Two’s Complement :011100
Aim8. Design a program for creating a machine which accepts string having equal no. of 1’s and 0’s.

#include <iostream>
#include<string.h>
using namespace std;

using namespace std;

int main()
{ charstr[50];
inti, n,CountZero=0,CountOne=0;

;
cout<<"\nEnter a string over input alphabets {0,1}\n";
cin>>str;

n=strlen(str);

for(i=0;i<n;i++)
{
if(str[i]=='0' )
{
CountZero++;

}
else
{
CountOne++;

if(CountOne==CountZero)

cout<<"String Accepted...";

else

cout<<"String Rejected...";

return 0;
}
OUTPUT:
Enter a string over input alphabets {0,1}
101010
String Accepted...

Enter a string over input alphabets {0,1}

1010101
String Rejected...

Aim9. Design a program for creating a machine which count number of 1’s and 0’s in a
given string.
#include <iostream>
#include<string.h>
using namespace std;

int main()
{ charstr[50];
inti, n,CountZero=0,CountOne=0;

;
cout<<"\nEnter a string over input alphabets {0,1}\n";
cin>>str;

n=strlen(str);

for(i=0;i<n;i++)
{
if(str[i]=='0' )
{
CountZero++;

}
else
{
CountOne++;

cout<<"NO of 1’s"<<CountOne<<endle;
cout<<"NO of 0’s"<<CountOne<<endle

return 0;
}

OUTPUT:
Enter a string over input alphabets {0,1}
101010
NO of 1’s:3
No of 0’s:3

Aim10.Design a Program for Mealy machine to find 1’s complement of a given binary
number.

Mealy machine for 1’s complement:

#include <stdio.h>
int main() {
charstr[100],f='a';
inti;
printf("Enter Any string over input alphabets {0,1} : \n ");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
switch(f)
{
case 'a': if(str[i]=='0') { printf("1");f='a'; } else {printf("0");f='a'; }

break;

}
}

return 0;
}
Enter Any string over input alphabets {0,1} :
Input:1010101
Output: 0101010

Aim11. Design a Program which will increment the given binary number by 1.
#include <stdio.h>
int main()
{
longint binary1, binary2;
inti = 0, remainder = 0, sum[20];
printf("Enter any binary number :");
scanf("%ld", &binary1);

while(binary1!= 0 || binary2 != 0)
{
sum[i++] = (binary1 % 10 + binary2 % 10 + remainder) % 2;
remainder = (binary1 % 10 + binary2 % 10 + remainder) / 2;
binary1 = binary1 / 10;
binary2 = binary2 / 10;
}

if(remainder != 0)
sum[i++] = remainder;
--i;
printf("Sum :");
while(i>= 0)
printf("%d", sum[i--]);

return 0;
}

OUTPUT:
Enter any binary number:110001
110010

Aim12. Design a Program to create PDA machine that accept the well-formed parenthesis.

// CPP program to check for balanced brackets.

#include <bits/stdc++.h>
using namespace std;

// function to check if brackets are balanced

boolareBracketsBalanced(string expr)
{
stack<char> s;
char x;

// Traversing the Expression

for (inti = 0; i<expr.length(); i++) {
{
if (expr[i] == '(' || expr[i] == '['
|| expr[i] == '{')
{
// Push the element in the stack
s.push(expr[i]);
continue;
}

// IF current current character is not opening

// bracket, then it must be closing. So stack
// cannot be empty at this point.
if (s.empty())
return false;

switch (expr[i]) {
case ')':

// Store the top element in x

x = s.top();
s.pop();
if (x == '{' || x == '[')
return false;
break;

case '}':

// Store the top element in b

x = s.top();
s.pop();
if (x == '(' || x == '[')
return false;
break;

case ']':

// Store the top element in x

x = s.top();
s.pop();
if (x == '(' || x == '{')
return false;
break;
} // switch ends here
} // for loop ends here

// Check Empty Stack

return (s.empty());
} function ends here

// Driver code
int main()
{
stringexpr = "{()}[]";

// Function call
if (areBracketsBalanced(expr))
cout<< "Balanced";
else
cout<< "Not Balanced";
return 0;
}

OUTPUT: Balanced

Aim13. Design a Push Down automata for L={(0^n1^n| n>=1}

#include <iostream>
#include<string.h>
using namespace std;
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()
{
inti,j, n;
char a[10];
cout<<"\nProgram For PDA Which Accpets Strings Of (0^n)(1^n)\n";
cout<<"\nEnter String::";
cin>>a;
n=strlen(a);
Stack st;
top=-1;
for(i=0;i<n/2;i++)
{
if(a[i]=='0' )
{

st.push(a[i]);
}
else

break;

if(i<n/2)
{
cout<<"String Rejected...";
exit(0);
}
for(j=i;j<n;j++)
{
if(a[i]=='1' )
{
st.pop(a[i]);

if(top==-1)
{
cout<<"\nString Accepted.\n";
}
else
{
cout<<"\nString Rejected.\n";
}
return 0;
}

OUTPUT:
INPUT:0011
String Accepted.

INPUT:0101
String Rejected.

R
Aim14. Design a PDA to accept WCW where w is any string and WR is reverse of that
string and C is a Special symbol.

Steps of design PDA:

1. Push all characters onto stack just before to C.
2. Now pop a or b off stack for next input symbol a or b respectively.
3. If after step 2 there is bottom symbol in stack Z then string is accepted otherwise
rejected.
Transition Function of PDA:

δ(q0, a, Z) = (q0, aZ)

δ(q0, a, a) = (q0, aa)
δ(q0, b, Z) = (q0, bZ)
δ(q0, b, b) = (q0, bb)
δ(q0, a, b) = (q0, ab)
δ(q0, b, a) = (q0, ba)

// this is decision step

δ(q0, c, a) = (q1, a)
δ(q0, c, b) = (q1, b)

δ(q1, b, b) = (q1, ε)
δ(q1, a, a) = (q1, ε)

δ(q1, ε, Z) = (qf, Z)
PDA state transition diagram

n
Aim14.Design a Turing machine that’s accepts the following languagea bncn where n>0

Steps to design Turing machine:

1. Mark first a as X and keep moving head to right direction.

2. Skip all remaining a’s and/or all Y’s while moving right.
3. Mark first b as Y and keep moving head to right direction.
4. Skip all b’s and / or all Z’s ,keep moving head to right direction.
5. Mark first c as Z and keep moving head to left direction.
6. Skip all b’s ,Y, Z and a’swhile moving left.
7. Move right as encounter first X, Repeat step 1 if there is unmarked a otherwise goto step 8
8. Moving head left direction , Skip all Y’sand all Z’s
9. If after step 8 Blank symbolB found, string is accepted otherwise rejected.
State Transition Diagram