Обобщенный недетерминированный конечный автомат

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

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

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

где R — совокупность всех регулярных выражений в алфавите Σ.

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

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

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