1.

Design a Finite Automata (FA) that accepts all strings

over S={0, 1} having three consecutive 1's as a substring.
Write a program to simulate this FA.
#include <iostream>
#include <string>

using namespace std;

// Function to simulate the finite automaton

bool hasThreeConsecutiveOnes(const string& input) {

enum State { q0, q1, q2, q3 };

State currentState = q0;

for (char c : input) {

switch (currentState) {
case q0:
if (c == '1') currentState = q1;
break;
case q1:
if (c == '1') currentState = q2;
else if (c == '0') currentState = q0;
break;
case q2:
if (c == '1') currentState = q3;
else if (c == '0') currentState = q0;
break;
 case q3:
// Once q3 is reached, remain in q3 as it's the
accepting state
return true;
}
}
// If we end in q3, return true, else false
return currentState == q3;
}

int main() {
string input;
cout << "Enter a binary string: ";
cin >> input;

if (hasThreeConsecutiveOnes(input)) {
cout << "The string has three consecutive '1's as a
substring." << endl;
} else {
cout << "The string does not have three consecutive
'1's as a substring." << endl;
}

return 0;
}
OUTPUT:

2.Design a Finite Automata (FA) that accepts all strings

over S={0, 1} having either exactly two 1's or exactly three
1's, not more nor less. Write a program to simulate this FA.

CODE:

#include <iostream>
#include <string>

using namespace std;

bool simulateDFA(const string& input) {

enum State { A, B, C, D, E };
State state = A;
for (char ch : input) {
switch (state) {
case A:
if (ch == '0') {
 state = A; // Stay in A
} else if (ch == '1') {
state = B; // Move to B
}
break;
case B:
if (ch == '0') {
state = B; // Stay in B
} else if (ch == '1') {
state = C; // Move to C
}
break;
case C:
if (ch == '0') {
state = B; // Return to B
} else if (ch == '1') {
state = D; // Move to D
}
break;
case D:

state = E;
break;
case E:

break;
}
 }

return state == C || state == D;

}

int main() {
string inputString;

cout << "Enter a binary string (composed of 0s and 1s):

";
cin >> inputString;

if (simulateDFA(inputString)) {
cout << "Valid String: Contains exactly two or three
1's" << endl;
} else {
cout << "Invalid String: Does not contain exactly two
or three 1's" << endl;
}

return 0;
}
OUTPUT:
3.Design a Finite Automata (FA) that accepts language
L1, over S={a, b}, comprising of all strings (of length 4
or more) having first two characters same as the last
two. Write a program to simulate this FA

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

bool isAcceptedByFA(const string& input) {

if (input.length() < 4) return false;

char first = input[0];

char second = input[1];

char secondLast = input[input.length() - 2];

char last = input[input.length() - 1];

return (first == secondLast && second == last);

}

int main() {
 string input;
cout << "Enter a string over {a, b}: ";
cin >> input;

if (isAcceptedByFA(input)) {
cout << "The string is accepted by the FA." << endl;
} else {
cout << "The string is not accepted by the FA." <<
endl;
}

return 0;
}

4.Design a Finite Automata (FA) that accepts language

L2, over S= {a, b} where L2= a(a+b)*b. Write a program
to simulate this FA.
#include <iostream>
#include <string>
using namespace std;

bool simulateFA(const string& input) {

int state = 0;

for (char c : input) {

switch (state) {
case 0:
if (c == 'a') {
state = 1;
} else {
return false;
}
break;

case 1:
if (c == 'a' || c == 'b') {
state = 2;
} else {
return false;
}
break;

case 2:
 if (c == 'a' || c == 'b') {
state = 2;
} else {
return false;
}
break;

default:
return false;
}
}

return (state == 2 && input.back() == 'b');

}

int main() {
string input;

cout << "Enter a string over {a, b}: ";

cin >> input;

if (simulateFA(input)) {
cout << "The string is accepted by the FA.\n";
} else {
cout << "The string is not accepted by the FA.\n";
}
 return 0;
}

5.Design a Finite Automata (FA) that accepts language

EVEN-EVEN over S={a, b}. Write a program to simulate
this FA.

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

bool simulateFA(const string& input) {

int state = 0;

for (char c : input) {

switch (state) {
case 0:
if (c == 'a') {
 state = 1;
} else if (c == 'b') {
state = 2;
} else {
return false;
}
break;

case 1:
if (c == 'a') {
state = 0;
} else if (c == 'b') {
state = 3;
} else {
return false;
}
break;

case 2:
if (c == 'a') {
state = 3;
} else if (c == 'b') {
state = 0;
} else {
return false;
}
break;
 case 3:
if (c == 'a') {
state = 2;
} else if (c == 'b') {
state = 1;
} else {
return false;
}
break;

default:
return false;
}
}

return state == 0;
}

int main() {
string input;

cout << "Enter a string over {a, b}: ";

cin >> input;

if (simulateFA(input)) {
cout << "The string is accepted by the FA.\n";
 } else {
cout << "The string is not accepted by the FA.\n";
}

return 0;
}

6.Write a program to simulate an FA that accepts

a. Union of the languages L1 and L2

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

bool simulateFA_L1(const string& input) {

return !input.empty() && input[0] == 'a';

}
bool simulateFA_L2(const string& input) {

return !input.empty() && input.back() == 'b';

}

bool simulateUnion(const string& input) {

return simulateFA_L1(input) || simulateFA_L2(input);
}

int main() {
string input;
cout << "Enter a string: ";
cin >> input;

if (simulateUnion(input)) {
cout << "The string is accepted by L1 ? L2.\n";
} else {
cout << "The string is not accepted by L1 ? L2.\n";
}

return 0;
}
b. Intersection of the languages L1 and L2

bool simulateIntersection(const string& input) {

return simulateFA_L1(input) && simulateFA_L2(input);
}

int main() {
string input;
cout << "Enter a string: ";
cin >> input;

if (simulateIntersection(input)) {
cout << "The string is accepted by L1 n L2.\n";
} else {
cout << "The string is not accepted by L1 n L2.\n";
}

return 0;
}
c. Language L1 L2 (concatenation)

bool simulateConcatenation(const string& input) {

for (size_t i = 0; i <= input.size(); ++i) {
string part1 = input.substr(0, i);
string part2 = input.substr(i);
if (simulateFA_L1(part1) && simulateFA_L2(part2)) {
return true;
}
}
return false;
}

int main() {
string input;
cout << "Enter a string: ";
cin >> input;

if (simulateConcatenation(input)) {
cout << "The string is accepted by L1L2
(concatenation).\n";
 } else {
cout << "The string is not accepted by L1L2
(concatenation).\n";
}

return 0;
}
7. Design a PDA and write a program for simulating
the machine which accepts the language {anbn where
n>0, S= {a, b}}.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool simulatePDA(const string& input) {

stack<char> pdaStack;
pdaStack.push('Z');

int state = 0;

for (char symbol : input) {

switch (state) {
 case 0:
if (symbol == 'a') {
pdaStack.push('A');
state = 1;
} else {
return false;
}
break;

case 1:
if (symbol == 'a') {
pdaStack.push('A');
} else if (symbol == 'b') {
if (!pdaStack.empty() && pdaStack.top() ==
'A') {
pdaStack.pop();
state = 2;
} else {
return false;
}
} else {
return false;
}
break;

case 2:
if (symbol == 'b') {
 if (!pdaStack.empty() && pdaStack.top() ==
'A') {
pdaStack.pop();
} else {
return false;
}
} else {
return false;
}
break;

default:
return false;
}
}

symbol Z
return state == 2 && pdaStack.size() == 1 &&
pdaStack.top() == 'Z';
}

int main() {
string input;

cout << "Enter a string (anbn format): ";

cin >> input;
 if (simulatePDA(input)) {
cout << "The string is accepted by the PDA." << endl;
} else {
cout << "The string is rejected by the PDA." << endl;
}

return 0;
}

8. Design a PDA and write a program for simulating

the machine which accepts the language {wXwr | w is
any string over S={a, b} and w^r is the reverse of that
string and X is a special symbol }.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool simulatePDA(const string& input) {
stack<char> pdaStack;
pdaStack.push('Z');
int state = 0;

for (char symbol : input) {

switch (state) {
case 0:
if (symbol == 'a' || symbol == 'b') {
pdaStack.push(symbol);
} else if (symbol == 'X') {
state = 1;
} else {
return false;
}
break;

case 1:
if (symbol == 'a' || symbol == 'b') {
if (!pdaStack.empty() && pdaStack.top() ==
symbol) {
pdaStack.pop();
} else {
return false;
}
} else {
return false;
 }
break;

default:
return false;
}
}
return state == 1 && pdaStack.size() == 1 &&
pdaStack.top() == 'Z';
}

int main() {
string input;

cout << "Enter a string (wXwr format): ";

cin >> input;

if (simulatePDA(input)) {
cout << "The string is accepted by the PDA." << endl;
} else {
cout << "The string is rejected by the PDA." << endl;
}

return 0;
}
9. Design and simulate a Turing Machine that accepts
the language a^n b^n c^n where n >0.

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

string tape;
int head;
string state;

bool simulateTM() {
head = 0;
state = "q0";

while (true) {
if (state == "q0") {
 if (tape[head] == 'a') {
tape[head] = 'X';
head++;
state = "q1";
} else if (tape[head] == 'Y' || tape[head] == 'Z' ||
tape[head] == '\0') {
state = "reject";
}
} else if (state == "q1") {
if (tape[head] == 'X' || tape[head] == 'Y') {
head++;
} else if (tape[head] == 'b') {
tape[head] = 'Y';
head++;
state = "q2";
} else if (tape[head] == 'c' || tape[head] == '\0') {
state = "reject";
}
} else if (state == "q2") {
if (tape[head] == 'X' || tape[head] == 'Y' ||
tape[head] == 'Z') {
head++;
} else if (tape[head] == 'c') {
tape[head] = 'Z'; // Mark 'c' as processed
head--; // Move left
state = "q3"; // Transition to q3
} else if (tape[head] == '\0') {
 state = "reject"; // Missing 'c'
}
} else if (state == "q3") {
if (tape[head] == 'X' || tape[head] == '\0') {
state = "q4"; // Check if all symbols are
processed
} else {
head--; // Move left to find the next unprocessed
symbol
}
} else if (state == "q4") {
return true; // Accept the input
} else if (state == "reject") {
return false; // Reject the input
}
}
}

int main() {
cout << "Enter the input string (format: a^n b^n c^n): ";
cin >> tape;

// Add a blank symbol at the end of the tape

tape += '\0';

if (simulateTM()) {
 cout << "The input string is ACCEPTED by the Turing
Machine." << endl;
} else {
cout << "The input string is REJECTED by the Turing
Machine." << endl;
}

return 0;
}

10. Design and simulate a Turing Machine which will

increment the given binary number by 1.

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

string tape; // The tape for the Turing Machine

int head; // The current head position
string state; // The current state of the machine

// Simulate the Turing Machine

void simulateTM() {
head = tape.size() - 1; // Start at the rightmost end
state = "q0"; // Start state

while (true) {
if (state == "q0") {
if (tape[head] == '0') {
tape[head] = '1'; // Replace '0' with '1'
state = "q2"; // Transition to termination state
} else if (tape[head] == '1') {
tape[head] = '0'; // Carry over by replacing '1'
with '0'
head--; // Move left
} else if (head < 0) { // If all digits are processed
state = "q3"; // Overflow case
}
} else if (state == "q2") {
state = "q_accept"; // Accept the input after
successful increment
} else if (state == "q3") {
tape = "1" + tape; // Add '1' at the leftmost position
state = "q_accept";
} else if (state == "q_accept") {
break; // Exit simulation
}
}
}
int main() {
cout << "Enter the binary number to increment: ";
cin >> tape;

simulateTM();

cout << "Binary number after increment: " << tape <<
endl;

return 0;
}