这是我的自动机,该语言的正则表达式是 (aaa*b|ba)a*
我想编写一个 C++ 程序来检查输入字符串是否被该语言接受。
该程序获取字符串并打印 Accepted
或Rejected
例如:
输入: aaaba - 输出:已接受
输入: baa - 输出:已接受
输入: aaa - 输出:被拒绝
最佳答案
#include <string>
#include <iostream>
bool check_string(const std::string& s) {
static constexpr int INV = -1;
static constexpr int INITIAL_STATE = 0;
static constexpr int ACCEPTING_STATE = 3;
static const int transition_table[5][2] = {
// a b
{ 1, 2 }, // 0
{ 4, INV }, // 1
{ 3, INV }, // 2
{ 3, INV }, // 3
{ 4, 3 } // 4
};
int state = INITIAL_STATE;
for (char c : s) {
if (c != 'a' && c != 'b') return false;
state = transition_table[state][c - 'a'];
if (state == INV) return false;
}
return state == ACCEPTING_STATE;
}
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr << "Usage: check str\n";
return 1;
}
if (check_string(argv[1]))
std::cout << "Accepted\n";
else
std::cout << "Rejected\n";
return 0;
}
关于c++ - 自动机,检查字符串是否被语言接受 | C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37084575/