Может ли кто-нибудь более умный, чем я, кратко описать сообществу SO алгоритм преобразования NFA в DFA? (Желательно в 500 слов или меньше.) Я видел схемы и лекции, которые только сбивали с толку то, что я думал, что когда-то знал. Я почти уверен в создании начальной таблицы переходов NFA из диаграммы состояний, но после этого я теряю DFA в эпсилонах и подмножествах.
1) В таблице переходов (дельта), в каком столбце представлены новые состояния DFA? Это первый столбец сгенерированных состояний?
2) В строке {2,3}, столбце 0 моего примера ниже, что означает {2,3} для NFA с точки зрения его диаграммы состояний? (Извините, я должен думать в картинках.) И я предполагаю, что это будет «возврат к входу 0» в DFA?
3) Любые простые «практические правила» перехода от таблицы к DFA или при распознавании принимаемых состояний результирующего DFA?
Конечно автономный
delta | 0 | 1 |
=======+=======+========+
{1} |{1} |{2} |
{2} |{3} |{2,3} |
{3} |{2} |{2,4} |
{2,3} |{2,3} |{2,3,4} |
{2,4} |{3,4} |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4} |{2,4} |{2,4} |
Изменить: вот таблица выше в точечном формате , приветствует Regexident.
digraph dfa {
rankdir = LR;
size = "8,5"
/* node [shape = doublecircle]; "1";*/
node [shape = circle];
"1" -> "1" [ label = "0" ];
"1" -> "2" [ label = "1" ];
"2" -> "3" [ label = "0" ];
"2" -> "2_3" [ label = "1" ];
"3" -> "2" [ label = "0" ];
"3" -> "2_4" [ label = "1" ];
"2_3" -> "2_3" [ label = "0" ];
"2_3" -> "2_3_4" [ label = "1" ];
"2_4" -> "2_3" [ label = "0" ];
"2_4" -> "2_3_4" [ label = "1" ];
"2_3_4" -> "2_3_4" [ label = "0" ];
"2_3_4" -> "2_3_4" [ label = "1" ];
"3_4" -> "2_4" [ label = "0" ];
"3_4" -> "2_4" [ label = "1" ];
}
А здесь в отрисованном виде:
Примечание: В таблице отсутствует какая-либо информация о принятии состояния, следовательно, и в графике.