алгоритм реализации DFA в виде связанного списка

Question

Я хочу знать, как реализовать DFA как связанный список в C / C ++ / Java.

Answer 1

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

Answer 2

Один связанный список не может эффективно представлять DFA.Вы можете рассматривать DFA как структуру данных ориентированного взвешенного графа, поскольку состояния - это вершины, переходы - это ребра, символы перехода - это веса.Существует два основных метода реализации структуры графа.

i) Список смежности: в основном он имеет V (количество вершин) связанных списков.Каждый список ссылок содержит вершины, которые имеют ребра к соответствующей вершине.Если у нас есть вершины (1,2,3) и ребра (1,2),(1,3),(2,1),(2,3),(3,3), соответствующий список адъюнктивов будет:

1->2->3
2->1->3
3->3

ii) Матрица смежности: Это матрица VxV с каждой записью в (i, j), символизирующей ребро из iкТот же самый пример, представленный выше, выглядит следующим образом (1 означает, что есть грань, 0 означает, что ее нет):

  1 2 3
1 0 1 1
2 1 0 1
3 0 0 1

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

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

Для реализации матрицы вы можете поместить веса непосредственно в матрицу вместо0,1 значения.

Если вы не хотите иметь дело с реализацией класса графов, есть библиотеки, такие как Boost Graph Library, которая содержит две реализации и все важные алгоритмы графов DFS для алгоритма кратчайшего пути Дейкстры.Вы можете посмотреть это с http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/index.html.

Answer 3

Первое, что мне пришло в голову, это то, что

создайте класс / структуру с именем state с двумя компонентами массива. один для государств, которые могут достигнуть нашего государства и один для тех, которые достижимы из нашего государства. Затем создайте связанный список, элементами которого являются ваши состояния.

вот моя реализация этого класса

class state
{
    private:
        string stateName;
        vector<state> states_before_me;
        vector<state> states_after_me;
        state* next;

        //methods of this state

}

Answer 4

Это определенно возможно, но было бы крайне неэффективно. То, что вы должны сделать, это просто сохранить все ваши состояния в списке ссылок, а затем для каждого состояния нужно будет сохранить таблицу переходов. Таблица перехода будет выглядеть примерно так:

'a' -> 2
'b' -> 5

, где ваш алфавит - {a,b}, а 2 и 5 - состояния, сохраненные в позициях 2 и 5 в связанном списке. Как я уже сказал, это определенно НЕ то, как вы хотели бы реализовать DFA, но это возможно.