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

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

10 голосов
/ 15 декабря 2010

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

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

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}   |

Редактировать: вот таблица выше в формате точка ,cheers 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

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

Ответы [ 2 ]

12 голосов
/ 15 декабря 2010

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

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

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

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

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

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

4 голосов
/ 15 декабря 2010

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

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

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

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

...