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