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

Question

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

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

此程序获取字符串并打印 Accepted 或 Rejected

例如：

输入： aaaba - 输出： 已接受

输入： baa - 输出： 已接受

输入： aaa - 输出： 拒绝

Answer 1

您完成了大部分工作，因为您的 DFA 绝对正确。让我完成剩下的工作。

让我们考虑一个函数，它将字符串作为参数，return true 或 false 取决于字符串是被接受还是被拒绝。

关键思想

主要思想是利用有限状态机状态，对字符串进行逐级处理。代码编写起来非常简单直接，因为它只是有限状态机遍历不同的状态，像自动机一样通过不同的状态处理输入字符串。

我们从状态 0 开始，然后按照您的自动机图

这是一个简短的描述。

如果字符串以 a 开头，则下一个状态为 1 。如果字符串以 b 开头，则下一个状态为 2，如果字符串两者都不开头，则该字符串被拒绝。

不管当前状态是 1 还是 2 而下一个字符不是 a，下一个字符是 a，字符串都会被拒绝。

如果下一个字符是 a ，则下一个状态是 3 或 4，具体取决于当前状态。

一旦我们解决了这个问题，如果当前状态是 3，那么我们只需要考虑 aa......aaa 直到字符串结束，如果在任何时候出现其他字符，则字符串将被拒绝。

如果当前状态是 4 ，我们再次处理 aa......aaa 但我们现在还必须看到在 aa.....aaa 之后也出现了一次 b 然后我们再次照顾 aa........aaa.

bool check_string(string str)
{
 int state = 0;    

 if(str[i] == 'a')
  { state = 1; ++i; }

 else if(str[i] == 'b')
  { state = 2; ++i; }

 else return false;

 if(str[i] != 'a')
  return false;

 else if(state == 1)
  {state = 4; ++i; }

 else if(state == 2)  
  {state = 3; ++i; }

 if(state == 3)
 {
   while(i < str.length())
   {
    if(str[i++] != 'a')
     return false;
   }
   return true;
 }

 if(state == 4)
 {
  while(i < str.length()&& str[i++] == 'a')
   {

   }
  if(i == str.length())
   return false;
  else if(str[i] == 'b')
  {
   while(i < str.length())
   {
    if(str[i++] != 'a')
     return false;
   }
   return true;
  }
  else return false;
}

Answer 2

#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++

automata, check string is accepted by language | C++

c++

finite-automata

automata