RUSTAMJI INSTITUTE OF TECHNOLOGY
BSF ACADEMY, TEKANPUR
Lab File for
CS501 (Theory of Computation)
Submitted by
XXXXXXX (0902CS2210XX)
[Link]. Computer Science & Engineering 5th Semester
(2022-2026 batch)
Subject Teacher File Checked by
Prof. Yograj Sharma Mr. Yashwant Pathak
TABLE OF CONTENTS
S. Experiment Description Page Remark
No. Nos.
1. Design a Program for creating machine that accepts 1-2
three consecutive one.
2. Design a Program for creating machine that accepts the 3-4
string always ending with 101.
3. Design a Program for Mode 3 Machine 5-6
4. Design a program for accepting decimal number 7-8
divisible by 2.
5. Design a program for creating a machine which accepts 9-10
string having equal no. of 1’s and 0’s.
6. Design a program for creating a machine which counts 11-12
no of ones and zeroes in a string.
7. Design a program to find 2’s complement of a given 13-15
binary number.
8. Design a program which will increment the given 16-17
binary number by 1.
9. Design a PDA to accept WCWR where W is any string 18-20
and WR is reverse of that string and C is a special
symbol.
10. Design a Turing machine that accepts the following 21-24
language: L= a^nb^nc^n over the alphabet abc where
n>0.
Experiment No.1
Objective : Design a Program for creating machine that accepts three
consecutive one.
Transition Graph:-
Program:-
#include <iostream>
using namespace std;
int main() {
string input;
int count = 0;
cout << "Enter a seProblem Statementuence of 1s and 0s: ";
cin >> input;
for (char c : input) {
if (c == '1') {
count++;
if (count == 3) {
cout << "Accepted! Three consecutive ones found." << endl;
return 0;
}
Ankita Soni
(0902CS221012) Page | 1
} else {
count = 0;
}
}
cout << "Not accepted. Three consecutive ones not found." << endl;
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 2
Experiment No.2
Objective : Design a Program for creating machine that accepts the string
always ending with 101.
Transition Graph:-
Program:-
#include <iostream>
#include <string>
using namespace std;
bool endsWith101(string str) {
int len = [Link]();
if (len < 3) {
return false;
}
return ([Link](len - 3) == "101");
}
int main() {
string input;
cout << "Enter a string: ";
Ankita Soni
(0902CS221012) Page | 3
cin >> input;
if (endsWith101(input)) {
cout << "Accepted! The string ends with '101'." << endl;
} else {
cout << "Rejected! The string does not end with '101'." << endl;
}
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 4
Experiment No.3
Objective : Design a Program for Word Length Mode 3 Machine.
Transition Graph:-
Program:-
#include <iostream>
using namespace std;
bool isDivisibleBy3(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return (sum % 3 == 0);
}
int main() {
Ankita Soni
(0902CS221012) Page | 5
int input;
cout << "Enter a number: ";
cin >> input;
if (isDivisibleBy3(input)) {
cout << "Accepted! The number is divisible by 3." << endl;
} else {
cout << "Rejected! The number is not divisible by 3." << endl;
}
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 6
Experiment No.4
Objective : Design a program for accepting decimal number divisible by 2.
Transition Graph:-
Program:-
#include <iostream>
#include <string>
using namespace std;
bool isDivisibleBy2(string str) {
int len = [Link]();
if (len == 0) {
return false;
}
int lastDigit = str[len - 1] - '0';
return (lastDigit % 2 == 0);
}
int main() {
Ankita Soni
(0902CS221012) Page | 7
string input;
cout << "Enter a decimal number using only 0s and 1s: ";
cin >> input;
if (isDivisibleBy2(input)) {
cout << "Accepted! The decimal number is divisible by 2." << endl;
} else {
cout << "Rejected! The decimal number is not divisible by 2." << endl;
}
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 8
Experiment No.5
Objective : Design a program for creating a machine which accepts string
having a Problem Statementual no. of 1’s and 0’s.
Transition Graph:-
Program:-
#include <iostream>
#include <string>
using namespace std;
bool hasEProblem StatementualOnesAndZeros(string str) {
int countOnes = 0;
int countZeros = 0;
for (char c : str) {
if (c == '1') {
countOnes++;
} else if (c == '0') {
countZeros++;
}
Ankita Soni
(0902CS221012) Page | 9
}
return (countOnes == countZeros);
}
int main() {
string input;
cout << "Enter a string: ";
cin >> input;
if (hasEProblem StatementualOnesAndZeros(input)) {
cout << "Accepted! The string has an eProblem Statementual number of
ones and zeros." << endl;
} else {
cout << "Rejected! The string does not have an eProblem Statementual
number of ones and zeros." << endl;
}
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 10
Experiment No.6
Objective : Design a program for creating a machine which count number of
1’s and 0’s in a given string.
Transition Graph:-
Program:-
#include <iostream>
#include <string>
using namespace std;
void countOnesAndZeros(string str) {
int ones = 0;
int zeros = 0;
for (char c : str) {
if (c == '1') {
ones++;
} else if (c == '0') {
zeros++;
}
}
cout << "Number of ones: " << ones << endl;
Ankita Soni
(0902CS221012) Page | 11
cout << "Number of zeros: " << zeros << endl;
}
int main() {
string input;
cout << "Enter a string: ";
cin >> input;
countOnesAndZeros(input);
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 12
Experiment No.7
Objective : Design a Program to find 2’s complement of a given binary number.
Transition Graph:-
Program:-
#include <iostream>
#include <string>
using namespace std;
string findTwosComplement(string binary) {
int n = [Link]();
int i;
// Find the first '1' from right to left
for (i = n - 1; i >= 0; i--) {
if (binary[i] == '1') {
break;
}
}
// If no '1' is found, return the original binary number
Ankita Soni
(0902CS221012) Page | 13
if (i == -1) {
return binary;
}
// Flip the bits after the first '1'
for (int j = i - 1; j >= 0; j--) {
if (binary[j] == '1') {
binary[j] = '0';
} else {
binary[j] = '1';
}
}
return binary;
}
int main() {
string binary;
cout << "Enter a binary number: ";
cin >> binary;
string twosComplement = findTwosComplement(binary);
cout << "Two's complement: " << twosComplement << endl;
return 0;
}
Ankita Soni
(0902CS221012) Page | 14
Output:-
Ankita Soni
(0902CS221012) Page | 15
Experiment No.8
Objective : Design a Program which will increment the given binary number by
1.
Transition Graph:-
Program:-
#include <iostream>
#include <string>
using namespace std;
string incrementBinary(string binary) {
int len = [Link]();
int carry = 1;
for (int i = len - 1; i >= 0; i--) {
if (binary[i] == '0' && carry == 1) {
binary[i] = '1';
carry = 0;
} else if (binary[i] == '1' && carry == 1) {
binary[i] = '0';
carry = 1;
}
Ankita Soni
(0902CS221012) Page | 16
}
if (carry == 1) {
binary = '1' + binary;
}
return binary;
}
int main() {
string binary;
cout << "Enter a binary number: ";
cin >> binary;
string result = incrementBinary(binary);
cout << "Result: " << result << endl;
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 17
Experiment No.9
Objective : Design a PDA to accept WCWR where w is any string and WR is
reverse of that string and C is a Special symbol.
Transition Graph:-
Program:-
#include <iostream>
#include <stack>
using namespace std;
bool isPDAAcceptable(string input) {
stack<char> pdaStack;
int i = 0;
char currentSymbol;
while (i < [Link]()) {
currentSymbol = input[i];
if (currentSymbol == 'C') {
Ankita Soni
(0902CS221012) Page | 18
if ([Link]()) {
return false;
}
[Link]();
} else {
[Link](currentSymbol);
}
i++;
}
while (![Link]()) {
if ([Link]() != input[i]) {
return false;
}
[Link]();
i++;
}
return true;
}
int main() {
string acceptedInput = "ABCDCBA";
string rejectedInput = "ABCDABA";
cout << "Accepted Input: " << acceptedInput << endl;
Ankita Soni
(0902CS221012) Page | 19
if (isPDAAcceptable(acceptedInput)) {
cout << "Accepted" << endl;
} else {
cout << "Rejected" << endl;
}
cout << "\nRejected Input: " << rejectedInput << endl;
if (isPDAAcceptable(rejectedInput)) {
cout << "Accepted" << endl;
} else {
cout << "Rejected" << endl;
}
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 20
Experiment No.10
Objective : Design a Turing machine that’s accepts the following language a n
b n c n where n>0.
Transition Graph:-
Program:-
#include <iostream>
#include <string>
using namespace std;
// Function to simulate the Turing machine
bool simulateTuringMachine(string input) {
int state = 0;
int i = 0;
int aCount = 0, bCount = 0, cCount = 0;
while (i < [Link]()) {
switch (state) {
case 0:
if (input[i] == 'a') {
Ankita Soni
(0902CS221012) Page | 21
aCount++;
i++;
state = 1;
} else {
return false;
}
break;
case 1:
if (input[i] == 'a') {
aCount++;
i++;
} else if (input[i] == 'b') {
bCount++;
i++;
state = 2;
} else {
return false;
}
break;
case 2:
if (input[i] == 'b') {
bCount++;
i++;
} else if (input[i] == 'c') {
cCount++;
i++;
Ankita Soni
(0902CS221012) Page | 22
state = 3;
} else {
return false;
}
break;
case 3:
if (input[i] == 'c') {
cCount++;
i++;
} else {
return false;
}
break;
}
}
if (aCount == bCount && bCount == cCount && cCount > 0) {
return true;
} else {
return false;
}
}
int main() {
string input;
cout << "Enter a string: ";
Ankita Soni
(0902CS221012) Page | 23
cin >> input;
if (simulateTuringMachine(input)) {
cout << "Accepted" << endl;
} else {
cout << "Rejected" << endl;
}
return 0;
}
Output:-
Ankita Soni
(0902CS221012) Page | 24