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