автомат, проверка строки принята языком | Переполнение стека

Это мой автомат, и это регулярное выражение для этого языка (aaa*b|ba)a*

введите описание изображения здесь

Я хочу, чтобы программа на C ++ для проверки входной строки принималась этим языком или нет.

Эта программа получает строку и печатает Accepted или же Rejected

Например:

вход: аааба — выход: Принято

вход: баа — выход: Принято

вход: ааа — выход: Отклонено

0

Решение

#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;
}
2

Другие решения

У вас большая часть работы, так как ваш DFA абсолютно правильный. Позвольте мне сделать оставшуюся работу.

Давайте рассмотрим функцию, которая будет принимать строку в качестве аргумента и возвращать истину или ложь в зависимости от того, принята строка или отклонена.

Ключевая идея

Основная идея состоит в том, чтобы использовать конечные автоматы и обрабатывать строку шаг за шагом. Код очень прост и прост в написании, потому что это просто конечный автомат, проходящий через различные состояния и обработка входной строки через различные состояния, как это делает ваш автомат.

Начнем с состояния 0 и следуем схеме ваших автоматов

Вот краткое описание.

если строка начинается с, следующее состояние — 1. Если строка начинается с b, следующее состояние равно 2, а если строка начинается с того или иного, строка отклоняется.

следующий символ — независимо от того, что текущее состояние равно 1 или 2, а следующий символ — не a, строка отклоняется.

если следующим символом является a, следующее состояние — 3 или 4 в зависимости от текущего состояния.

Как только мы позаботимся об этом, если текущее состояние равно 3, то нам нужно только рассмотреть aa …… aaa до конца строки, и если какой-либо другой символ встречается в любой точке, строка отклоняется.

Если текущее состояние равно 4, мы снова позаботимся о 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;
}
1