Обобщенный недетерминированный конечный автомат
В теории вычислений обобщенный недетерминированный конечный автомат ( GNFA ), также известный как автомат выражений или обобщенный недетерминированный конечный автомат , представляет собой разновидность недетерминированный конечный автомат (NFA), в котором каждый переход помечен любым регулярным выражением . GNFA считывает блоки символов из входных данных, которые составляют строку, определенную регулярным выражением при переходе. Существует несколько различий между стандартным конечным автоматом и обобщенным недетерминированным конечным автоматом. GNFA должен иметь только одно начальное состояние и одно состояние принятия, и они не могут быть одним и тем же состоянием, тогда как NFA или DFA могут иметь несколько состояний принятия, и начальное состояние может быть состоянием принятия. GNFA должен иметь только один переход между любыми двумя состояниями, тогда как NFA и DFA допускают множество переходов между состояниями. В GNFA состояние имеет единственный переход в каждое состояние машины, хотя часто принято игнорировать переходы, помеченные пустым набором, при рисовании обобщенных недетерминированных конечных автоматов.
Формальное определение
[ редактировать ] | Этот раздел необходимо отредактировать, чтобы Википедии он соответствовал Руководству по стилю . В частности, у него проблемы с MOS:MATHSPECIAL - Используйте <math>... \setminus ...</math> или <math>... \smallsetminus ...</math> вместо U+2216 ∖ УСТАНОВИТЬ МИНУС или U+005C \ ОБРАТНЫЙ СОЛИДУС для вычитания множеств. ( февраль 2024 г. ) |
GNFA можно определить как набор из 5 элементов ( S , Σ, T , s , a ), состоящий из
- конечное множество состояний ( S );
- конечное множество, называемое алфавитом (Σ);
- перехода функция ( T : ( S ∖ { a }) × ( S ∖ { s }) → R );
- начальное состояние ( s ∈ S );
- состояние принятия ( a ∈ S );
где R — совокупность всех регулярных выражений в алфавите Σ.
Функция перехода принимает в качестве аргумента пару двух состояний и выводит регулярное выражение (метку перехода). Это отличается от других конечных автоматов, которые принимают на вход одно состояние и входные данные из алфавита (или пустую строку в случае недетерминированных конечных автоматов) и выводят следующее состояние (или набор возможных состояний в случае недетерминированных конечных автоматов). DFA S или NFA можно легко преобразовать в GNFA, а затем GNFA можно легко преобразовать в регулярное выражение , многократно сжимая его части до отдельных ребер до тех пор, пока = { s , a }. Аналогично, GNFA можно свести к NFA, заменяя операторы регулярных выражений на новые ребра до тех пор, пока каждое ребро не будет помечено регулярным выражением, соответствующим одной строке длиной не более 1. NFA, в свою очередь, можно свести к DFA с помощью конструкции powerset . Это показывает, что GNFA признают тот же набор формальных языков, что и DFA и NFA.
Ссылки
[ редактировать ]- Йо-Суб Хан и Дерик Вуд . «Обобщение обобщенных автоматов: автоматы выражения». В: 9-я Международная конференция по внедрению и применению автоматов , CIAA 2004, Кингстон, Канада, 22–24 июля 2004 г., Пересмотренные избранные статьи, LNCS 3317, стр. 156–166. два : 10.1007/b105090
- Майкл Сипсер . 2006. Введение в теорию вычислений (2-е изд.). Международное издательство Томсон.
Внешние ссылки
[ редактировать ]- Графическое описание GNFA и процесс преобразования NFA в регулярное выражение с использованием GNFA можно найти по адресу [1].