определение e-AFI для AFD

e-AFI в AFD

Теперь мы хотим показать, что язык, распознаваемый автомат с пустыми переходами также может быть выполнен недетерминированным автоматом без пустых переходов (определение e-AFI в сторону преобразователь частоты). Эта операция потребует добавления новых переходов в автомат.

Любой язык, признанный АФН с ε-переходами можно распознать по АФН (без ε-переходов), имеющей такое же количество состояний.

Построение АФН, эквивалентной автомату с ε-переходами, путем расширения δ до δ1 (транзитивное замыкание — это все состояния, в которые может попасть состояние при данном переходе).

Первый шаг: добавление ε-переходов транзитивным замыканием.

Для всех состояний q, достижимых из p посредством ε-перехода (в несколько шагов), добавим прямой ε-переход из p в q. Таким образом, мы расширяем функцию δ: δ1(p, ε) = все состояния, достижимые из p посредством ε–перехода.

Второй шаг: добавление дополнительных переходов и дополнительных начальных состояний, затем удаление ε-переходов.

Начальные состояния — это все состояния, достижимые из начальных состояний посредством ε-перехода.

К любому переходу от p к q по букве добавим переходы от p к r с той же буквой для всех ε-переходов от q к r: δ1(p, a) = δ(p, a) ∪ ( ∪_{q∈δ(p, а)} δ1(q, ε)).

Удаляем все ε–переходы

Пример

Принцип алгоритма состоит в замене каждого пути длины 1, начинающегося с эпсилон-перехода, новым переходом, описывающим этот путь.

Есть два пути длины 1, которые начинаются с перехода на эпсилон:

• (1, ε, 3)(3, б, 3)
•  (1, е, 3)(3, в, 4)

К автомату добавлены два новых перехода, которые суммируют эти два пути:

• (1, б, 3)
• (1, в, 4)

И удаляем переход (1, ε, 3).

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

Использование эпсилон-переходов иногда позволяет более четко описать язык. Это также позволяет упростить описание некоторых операций (например, объединение или конкатенация -> см. автомат Томпсон).

Существование эпсилон-переходов делает автомат недетерминированным, поскольку всегда есть возможность позаимствовать такой переход, даже если существует обычный переход, который можно было бы позаимствовать.

Другой пример

Рассмотрим следующий автомат:

Для этого сначала необходимо вычислить для каждого состояния ε-преемников каждого состояния p, то есть множество состояний q таких, что существует путь, образованный только ε-переходами, начинающийся из p и приходящий в кв.

Вычислим ε-преемников каждого состояния: Succε(p) = {q, r}, Succε(q) = {r}, Succε(r) = ∅.

Получаем следующий НКА:

Затем вы можете определить его с помощью метода NFA в DFA или определить непосредственно в его форме с переходом спилона, как в следующем примере.

Давайте возьмем автомат и преобразуем его в DFA:

Первым шагом является вычисление эпсилон-замыканий для каждого состояния этого автомата:

Для каждого состояния замыкания вычисляем его переходы в алфавите без эпсилон:

Для каждого состояния, полученного переходами, вычисляем замыкание:

Пусть {p,q,r} = P; {q,r} = Q и {r} = R. Получаем следующий автомат: