автомат, проверка строки принята языком | Переполнение стека
Это мой автомат, и это регулярное выражение для этого языка (aaa*b|ba)a*
Я хочу, чтобы программа на C ++ для проверки входной строки принималась этим языком или нет.
Эта программа получает строку и печатает Accepted или же Rejected
Например:
вход: аааба — выход: Принято
вход: баа — выход: Принято
вход: ааа — выход: Отклонено
Решение
#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;
}
Другие решения
У вас большая часть работы, так как ваш 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;
}