Рубрики

Преобразование из NFA в DFA

NFA может иметь ноль, один или несколько ходов из заданного состояния для данного входного символа. NFA также может иметь значения NULL (движения без входного символа). С другой стороны, DFA имеет один и только один ход из заданного состояния для данного входного символа.

Преобразование из NFA в DFA
Предположим, что существует NFA N <Q, ∑, q0, δ, F>, который распознает язык L. Тогда DFA D <Q ', ∑, q0, δ', F '> можно построить для языка L как:
Шаг 1: Первоначально Q '= ɸ.
Шаг 2: Добавьте q0 к Q '.
Шаг 3: Для каждого состояния в Q 'найдите возможный набор состояний для каждого входного символа, используя функцию перехода NFA. Если этот набор состояний отсутствует в Q ', добавьте его в Q'.
Шаг 4: Конечное состояние DFA будет все состояния с содержанием F (конечные состояния NFA)

пример
Рассмотрим следующую NFA, показанную на рисунке 1.

Ниже приведены различные параметры для NFA.
Q = {q0, q1, q2}
∑ = (а, б)
F = {q2}
δ (переходная функция NFA)

Шаг 1: Q '= ɸ
Шаг 2: Q '= {q0}
Шаг 3: Для каждого состояния в Q 'найдите состояния для каждого входного символа.
В настоящее время состояние в Q 'равно q0, найдите ходы от q0 на входных символах a и b, используя функцию перехода NFA, и обновите таблицу переходов DFA.

δ '(переходная функция DFA)

Теперь {q0, q1} будет рассматриваться как одно состояние. Поскольку его запись не в Q ', добавьте его в Q'.
Так что Q '= {q0, {q0, q1}}

Теперь переходы из состояния {q0, q1} для разных входных символов отсутствуют в таблице переходов DFA, мы рассчитаем это следующим образом:
δ '({q0, q1}, a) = δ (q0, a) ∪ δ (q1, a) = {q0, q1}
δ '({q0, q1}, b) = δ (q0, b) ∪ δ (q1, b) = {q0, q2}
Теперь мы обновим таблицу переходов DFA.

δ '(переходная функция DFA)

Теперь {q0, q2} будет рассматриваться как одно состояние. Поскольку его запись не в Q ', добавьте его в Q'.
Так что Q '= {q0, {q0, q1}, {q0, q2}}

Теперь переходы из состояния {q0, q2} для разных входных символов отсутствуют в таблице переходов DFA, мы рассчитаем это следующим образом:
δ '({q0, q2}, a) = δ (q0, a) ∪ δ (q2, a) = {q0, q1}
δ '({q0, q2}, b) = δ (q0, b) ∪ δ (q2, b) = {q0}
Теперь мы обновим таблицу переходов DFA.

δ '(переходная функция DFA)

Так как новое состояние не генерируется, мы закончили с преобразованием. Конечным состоянием DFA будет состояние, в котором компонентом является q2, то есть {q0, q2}

Ниже приведены различные параметры для DFA.
Q '= {q0, {q0, q1}, {q0, q2}}
∑ = (а, б)
F = {{q0, q2}} и переходная функция δ ', как показано выше. Окончательный DFA для вышеупомянутого NFA был показан на рисунке 2.

Примечание. Иногда преобразовать регулярное выражение в DFA нелегко. Сначала вы можете преобразовать регулярное выражение в NFA, а затем NFA в DFA.

Вопрос: Число состояний в минимальном детерминированном конечном автомате, соответствующем регулярному выражению (0 + 1) * (10), составляет ____________.
Решение: во- первых, мы сделаем NFA для вышеприведенного выражения. Чтобы сделать NFA для (0 + 1) *, NFA будет в том же состоянии q0 на входном символе 0 или 1. Затем для конкатенации мы добавим два хода (q0 к q1 для 1 и q1 к q2 для 0), как показано на рисунке 3.

Эта статья предоставлена Sonal Tuteja.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Преобразование из NFA в DFA

0.00 (0%) 0 votes