Преобразование 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 выглядит следующим образом -