c++ - 自动机,检查字符串是否被语言接受 | C++

标签 c++ finite-automata automata

这是我的自动机,该语言的正则表达式是 (aaa*b|ba)a*

enter image description here

我想编写一个 C++ 程序来检查输入字符串是否被该语言接受。

该程序获取字符串并打印 AcceptedRejected

例如:

输入: 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/

相关文章:

C++ 解引用数组

C++随机引擎不是真正随机的

algorithm - 来自 "Programming Pearls"的方程式 - 有人可以解释一下吗?

python - 将某种 XML/Json 文件编译成 Graphiz/有限状态自动机。有什么建议么?

context-free-grammar - 确定给定的语言是否为常规/上下文无关/非上下文无关

c++ - 在 C++ 状态机中实现事件条件

c++ - 第二个参数在std::string myString {“Hello”, “World”}中做什么?

ruby - 基于匹配的回调正则表达式

java - 有限自动机字符串匹配器

state-machine - 堆栈大小受限的 PDA 接受哪些类型的语言?