Преобразование NDFA в DFA
Постановка задачи
Позволять X = (Qx, ∑, δx, q0, Fx)быть NDFA, который принимает язык L (X). Мы должны разработать эквивалентный DFAY = (Qy, ∑, δy, q0, Fy) такой, что L(Y) = L(X). Следующая процедура преобразует NDFA в эквивалентный DFA -
Алгоритм
Input - NDFA
Output - Эквивалент DFA
Step 1 - Создать таблицу состояний из заданного NDFA.
Step 2 - Создайте пустую таблицу состояний для возможных входных алфавитов для эквивалентного DFA.
Step 3 - Отметьте начальное состояние DFA как q0 (то же, что и NDFA).
Step 4- Найдите комбинацию состояний {Q 0 , Q 1 , ..., Q n } для каждого возможного входного алфавита.
Step 5 - Каждый раз, когда мы создаем новое состояние DFA под столбцами входного алфавита, мы должны снова применить шаг 4, в противном случае перейти к шагу 6.
Step 6 - Состояния, которые содержат любое из конечных состояний NDFA, являются конечными состояниями эквивалентного DFA.
пример
Давайте рассмотрим NDFA, показанный на рисунке ниже.
| q | δ (q, 0) | δ (д, 1) |
|---|---|---|
| а | {a, b, c, d, e} | {d, e} |
| б | {c} | {e} |
| c | ∅ | {b} |
| d | {e} | ∅ |
| е | ∅ | ∅ |
Используя описанный выше алгоритм, мы находим его эквивалент DFA. Таблица состояний DFA показана ниже.
| q | δ (q, 0) | δ (д, 1) |
|---|---|---|
| [а] | [a, b, c, d, e] | [d, e] |
| [a, b, c, d, e] | [a, b, c, d, e] | [b, d, e] |
| [d, e] | [e] | ∅ |
| [b, d, e] | [c, e] | [e] |
| [e] | ∅ | ∅ |
| [c, e] | ∅ | [b] |
| [b] | [c] | [e] |
| [c] | ∅ | [b] |
Диаграмма состояний DFA выглядит следующим образом -
