Краткое описание преобразования NFA в DFA?

Может ли кто-нибудь более умный, чем я, кратко описать сообществу 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" ];
}

А здесь в отрисованном виде:

Rendered dot graph

Примечание: В таблице отсутствует какая-либо информация о принятии состояния, следовательно, и в графике.

10
задан Regexident 20 June 2013 в 11:15
поделиться