Code:
#include <iostream>
#include <stack>
#include <string>
class PDA {
private:
std::stack<char> stack; // Stack to simulate the PDA
public:
bool transition(char symbol) {
/*
Simulates the transition function of the PDA.
:param symbol: Current input symbol
:return: True if the transition is valid, False otherwise
*/
if (symbol == '0') {
// Push '0' onto the stack for each '0' in input
[Link]('0');
} else if (symbol == '1') {
// Pop '0' from the stack for each '1' in input, if possible
if (![Link]() && [Link]() == '0') {
[Link]();
} else {
return false; // Reject if no matching '0' on the stack
}
} else {
return false; // Reject if the symbol is not '0' or '1'
}
return true;
}
bool accept(const std::string &input_string) {
/*
Determines if the input string is accepted by the PDA.
:param input_string: String to process
:return: True if accepted, False otherwise
*/
for (char symbol : input_string) {
if (!transition(symbol)) {
return false;
}
}
// Accept if the stack is empty after processing all input
return [Link]();
}
};
int main() {
PDA pda;
std::string input_string;
std::cout << "Enter a string to test (or type 'exit' to quit):" << std::endl;
while (true) {
std::cout << "Input: ";
std::cin >> input_string;
if (input_string == "exit") {
break;
}
bool result = [Link](input_string);
std::cout << "Result: " << (result ? "Accepted" : "Rejected") << std::endl;
}
return 0;
}