Вопрос по c++ – Реализация кода для симуляции недетерминированного конечного автомата в c ++

10

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

У меня есть этот входной файл:

<code>6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
3
aaabcccc
aabbbbcdc
acdddddd
</code>

Входные данные начинаются с 4 целых чисел, первое - номер состояния автомата, следующее - число переходов автомата, третье число - начальное состояние, а затем число конечных состояний. затем идут конечные состояния (в примере конечные состояния 2 и 5).

Затем идут N строк (N - количество переходов), каждая из которых содержит 2 целых числа и символ I, J и C, представляющих состояния, в которых происходит переход, т. Е. Переход из состояния i в состояние J с символом C. После этой строки идет одно целое число S, которое будет содержать количество проверяемых строк, затем S строк с соответствующими строками.

Вывод этой программы должен быть:

<code>Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
acdddddd Accepted
</code>

Должно быть указано, принята строка или отклонена. До сих пор я только кодировал работу с вводом.

I don't know how would be most convenient to represent the automaton, Должен ли я просто использовать массивы? Какую логику я бы применил к массивам? Есть ли способ сделать это, не зная заранее алфавит автомата? Нужна ли структура данных для представления автоматов? Я немного застрял в этом задании и хотел бы, чтобы некоторые идеи, псевдокод или идеи сделали это. Код на другом языке? Я не хочу решения, потому что я хочу выполнить свое задание, но если бы я мог использовать некоторую помощь

Я не эксперт по этой теме, может задать здесь глупый вопрос. почему у вас есть два перехода, когда вы начинаете с одного и того же состояния, и вы попадаете в разные состояния с одним и тем же событием / символом, запускающим переход? это означает, что сами государства тоже имеют внутреннее состояние? sergico
@sergico: именно поэтому такой граф называется недетерминированным, иногда есть несколько переходов. Поэтому вам нужно некоторое отслеживание. Все такие автоматы могут быть представлены (гораздо большим) детерминистским автоматом, но это может не стоить его вычислять. Matthieu M.

Ваш Ответ

1   ответ
5

tr для переходов гдеtr[(i, c)] = j если есть переход отi состояние дляj состояние черезc, массив для конечных состоянийfs[m] гдеm число конечных состояний и целое число для начального состоянияs0.

Сильфон - это рамка класса с такими свойствами:

class Automata
{
public:
    Automata(int start) : s0(start)
    {}

    void add_transition(int i, int j, char c) {
        //...
    }

    void add_final_state(int i) {
        //...
    }

    bool validate_string(const std::string& str) {
        //...
    }
private:
    std::map<std::pair<int, char>, int> tr; // transitions
    std::vector<int> fs; // final states
    int s0; // initial state
};
Да, именно так.
Что такое функция проверки строки? novaKid
Ах, ты прав @Matthieu M. Я отредактирую свой ответ.
Неплохо, за исключениемtransitions массив. Может быть несколько способов перехода из одного состояния в другое. Лучшее представление - иметь отображение (State, Event) - & gt; Государственный.std::map< std::pair<int, char>, int > будет естественно вписаться сюда.
То есть, я думаю, что мне нужно продолжать пробовать цепочку, и если в конце этой обработки строка находится в окончательном состоянии, то это правильно? novaKid

Похожие вопросы