Автомат с пустым переходом

Сложность

Легкий 25%

Контенус

Мы привыкли рисовать автомат с пустым переходом, изображая состояния кружками, начальное состояние указывая входящей стрелкой, принимающие состояния двойным кружком или исходящей стрелкой, а переход из состояния q в состояние q' чтением буквы α стрелкой стрелка, идущая от q к q' и отмеченная α.

Конечный автомат A с эпсилон-переходом (или автомат с пустым переходом) — это тройка (Vt, Q, T), где

Vt — словарь автомата;
Q — конечное множество состояний автомата;
T : Q × (Vt ∪ ε) → Q — частичное отображение, называемое переходной функцией автомата.

Обратите внимание, что обозначение q(α)→q' становится двусмысленным, так как теперь оно принимает два разных значения в зависимости от того, рассматривается ли α как буква (или как символ ε) и тогда будет одиночный переход, или как слово (длины 1 или 0), и тогда может быть произвольное количество переходов (из которых максимум один будет непустым).

Опять же, понятие деривации не изменилось, а понятие дерева деривации
требует лишь тривиальной адаптации, так как теперь есть переходы, помеченные ε. Вычисления автомата с пустыми переходами позволяют пройти любое количество пустых переходов во время выполнения. Таким образом, количество пройденных состояний больше не будет равно количеству букв входного слова, а может быть намного больше. Дерево вычислений автомата с пустыми переходами вдруг оказывается менее интересным инструментом, чем для недетерминированных автоматов без пустых переходов.

От автомата с пустым переходом к распознаваемым словам

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

Если мы возьмем приведенный выше автомат на слове aaaab:

p(aaaab) → q(aaab)→r(aaab)→s(aaab)→s(aab)→s(ab)→s(b)→q(b)→r – конечное состояние

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

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

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

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

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

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

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

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