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

Может ли кто-нибудь намного ярче, чем я кратко описать SO-сообществу алгоритм преобразования NFA в DFA? (Желательно в 500 слов или меньше.) Я видел диаграммы и лекции, которые только путали то, что, как я думал, я когда-то знал. Я в основном уверен в создании начальной таблицы перехода NFA из диаграммы состояния, но после этого я теряю DFA в эпсилон и подмножества.

1) В таблице перехода (дельта), в каком столбце представлены новые состояния DFA? Это первый столбец сгенерированных состояний?

2) В строке {2,3}, col 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" ];
}

И здесь в визуализированной форме:

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

Ответ 1

Когда вы создаете DFA из NFA, вы в основном находите те наборы состояний, которые NFA может быть за один раз (например, имитация NFA). Сначала вы начинаете с состояния начала, а затем находите все состояния, которые могут быть достигнуты с помощью переходов epsilon. Этот набор состояний формирует начальное состояние полученного DFA. Затем вы выполняете исходящие переходы из этого состояния. Это может привести к другому состоянию NFA, потому что вы снова найдете состояния, доступные через эпсилонные входы, и вы получите еще один набор состояний NFA, который станет новым статусом DFA. Вы выполняете этот процесс, пока не закончите.

Дело в том, что результирующие состояния DFA станут наборами старых состояний NFA, которые совместимы (относительно переходов эпсилон). Эти наборы также могут перекрываться, что не является ошибкой. И теперь я могу ответить на ваши вопросы:

1) Первый столбец представляет новые состояния DFA. Он показывает состояния состояний NFA, которые формируют заданное состояние DFA.

2) Ваше предположение верно, это означает, что loopback указывает состояние {2,3} на вход 0.

3) Таблицу DFA можно легко построить из этой таблицы, просто назовите свои состояния буквами. Любые состояния DFA, которые содержат по крайней мере одно принимающее состояние NFA, также станут состояниями принятия в DFA.

Надеюсь, я был достаточно ясным.

Ответ 2

Основная идея Вероятно, чтобы понять, что DFA - это своего рода машина, которая накладывается поверх NFA. В то время как NFA проще с точки зрения количества узлов или его связи с проблемой, он довольно тонкий и компилируется (он переходит в правильное состояние, в зависимости от того, что может быть). Dfa намного сложнее с точки зрения узлов, которые он содержит, но имеет действительно простые правила, поскольку для любого заданного ввода существует ровно одно состояние вывода.

Трансформация довольно проста. каждое состояние в DFA является подмножеством состояний в NFA. Начальное состояние DFA - это набор, содержащий только начальное состояние NFA, а состояние accept для DFA - это все его состояния, которые принимают состояние NFA как элементы.

Переходы в DFA - единственная сложная сторона. NFA не является детерминированным, поскольку его выходные состояния для данного входа представляют собой набор состояний, но DFA имеет наборы соответствующих состояний NFA как свои собственные состояния, представляющие, какой из состояний NFA может быть включен автомат. Таким образом, выход состояние любого состояния DFA для любого заданного входа является объединением выходных состояний всех состояний NFA этого состояния DFA.

В терминах реальных реализаций DFA имеет население штата, которое по сути является полномочием государств NFA. IE, 2 ^ (n) для n состояний NFA. На практике это обычно намного меньше, но нет общего способа предсказать его размер, поэтому некоторые практические реализации NFA для DFA генерируют состояния DFA динамически по мере их достижения и кэшируют их. Как только определенное количество состояний создано, наименее используемое последнее время отбрасывается, ограничивая размер кеша.