Обобщенный недетерминированный конечный автомат - Generalized nondeterministic finite automaton

в теория вычислений, а обобщенный недетерминированный конечный автомат (GNFA), также известный как автомат выражения или обобщенный недетерминированный конечный автомат, является разновидностью недетерминированный конечный автомат (NFA), где каждый переход помечен любым регулярное выражение. GNFA считывает блоки символов из ввода, которые составляют строку, как определено регулярным выражением при переходе. Есть несколько различий между стандартным конечным автоматом и обобщенным недетерминированным конечным автоматом. У GNFA должно быть только одно начальное состояние и одно состояние принятия, и они не могут быть одним и тем же состоянием, тогда как NFA или DFA могут иметь несколько состояний принятия, и начальное состояние может быть состоянием принятия. GNFA должен иметь только один переход между любыми двумя состояниями, тогда как NFA и DFA допускают многочисленные переходы между состояниями. В GNFA состояние имеет один переход к каждому состоянию в машине, хотя часто принято игнорировать переходы, помеченные пустым набором, при рисовании обобщенных недетерминированных конечных автоматов.

Формальное определение

GNFA можно определить как 5-кратный, (S, Σ, Т, s, а), состоящий из

• а конечный набор государств (S);
• конечное множество, называемое алфавитом (Σ);
• переход функция (Т : (S ∖ {а}) × (S ∖ {s}) → р);
• начальное состояние (s ∈ S);
• состояние принятия (а ∈ S);

где р - это набор всех регулярных выражений над алфавитом Σ.

Функция перехода принимает в качестве аргумента пару двух состояний и выводит регулярное выражение (метку перехода). Это отличается от других конечных автоматов, которые принимают на входе одно состояние и ввод из алфавита (или пустую строку в случае недетерминированных конечных автоматов) и выводят следующее состояние (или набор возможных состояний в случае недетерминированных конечных автоматов). А DFA или NFA можно легко преобразовать в GNFA, а затем GNFA можно легко преобразовать в регулярное выражение путем многократного сворачивания его частей в отдельные края, пока S = {s, а}. Точно так же GNFA можно уменьшить до NFA, заменив операторы регулярных выражений на новые ребра, пока каждое ребро не будет помечено регулярным выражением, совпадающим с единственной строкой длиной не более 1. NFA, в свою очередь, можно свести к DFA с помощью конструкция электростанции. Это показывает, что GNFA распознают один и тот же набор формальные языки как DFA и NFA.

использованная литература

• Йо-Суб Хан и Дерик Вуд. «Обобщение обобщенных автоматов: автоматы выражений». В: 9-й Международный Конференция по внедрению и применению автоматов, CIAA 2004, Кингстон, Канада, 22–24 июля 2004 г., Пересмотренные избранные статьи, LNCS 3317. С. 156–166. Дои:10.1007 / b105090
• Майкл Сипсер. 2006. Введение в теорию вычислений (2-е изд.). International Thomson Publishing.

внешние ссылки

• Графическое описание GNFA и процесса преобразования NFA в регулярное выражение с помощью GNFA можно найти по адресу [1]