Автомат Бюхи - Википедия - Büchi automaton

Автомат Бюхи
Автомат Бюхи с двумя состояниями, и , первое из которых является начальным, а второе - принимающим. Его входные данные - бесконечные слова над символами . Например, он принимает бесконечное слово , куда обозначает бесконечное повторение строки. Он отвергает бесконечное слово .

В Информатика и теория автоматов, а детерминированный автомат Бюхи это теоретическая машина, которая либо принимает, либо отклоняет бесконечные входные данные. Такая машина имеет набор состояний и функцию перехода, которая определяет, в какое состояние машина должна перейти из своего текущего состояния при чтении следующего входного символа. Некоторые состояния принимают состояния, и одно состояние является начальным. Машина принимает ввод тогда и только тогда, когда она будет проходить через состояние приема бесконечно много раз при чтении ввода.

А недетерминированный автомат Бюхи, позже называемый просто Büchi автомат, имеет функцию перехода, которая может иметь несколько выходов, что приводит к множеству возможных путей для одного и того же входа; он принимает бесконечный ввод тогда и только тогда, когда принимает некоторый возможный путь. Детерминированные и недетерминированные автоматы Бюхи обобщают детерминированные конечные автоматы и недетерминированный конечный автомат к бесконечным входам. Каждый тип ω-автоматы. Автоматы Бюхи распознают ω-регулярные языки, версия бесконечного слова обычные языки. Они названы в честь швейцарского математика. Юлиус Рихард Бючи, который изобрел их в 1962 году.[1]

Автоматы Бюхи часто используются в проверка модели как теоретико-автоматная версия формулы в линейная темпоральная логика.

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

Формально детерминированный автомат Бюхи кортеж А = (Q, Σ, δ,q0,F), который состоит из следующих компонентов:

  • Q это конечный набор. Элементы Q называются состояния из А.
  • Σ - конечное множество, называемое алфавит из А.
  • δ:Q × Σ →Q это функция, называемая функция перехода из А.
  • q0 является элементом Q, называется начальное состояние из А.
  • F⊆Q это условие приема. А принимает именно те прогоны, в которых хотя бы одно из бесконечно часто встречающихся состояний находится вF.

В (недетерминированный) Büchi автомат, функция перехода δ заменяется отношением перехода Δ, которое возвращает набор состояний, а единственное начальное состояние q0 заменяется набором я начальных состояний. Обычно термин «автомат Бюхи» без квалификатора относится к недетерминированным автоматам Бюхи.

Для более полного формализма см. Также ω-автомат.

Свойства закрытия

Набор автоматов Бюхи закрыт под следующие операции.

Пусть A = (QА, Σ, ΔА,яА,FА) и B = (QB, Σ, ΔB,яB,FB) - автоматы Бюхи и C = (QC, Σ, ΔC,яC,FC) быть конечный автомат.

  • Союз: Существует автомат Бюхи, распознающий язык L (A) ∪L (B).
Доказательство: Если предположить, w.l.o.g., QА∩QB пусто, то L (A) ∪L (B) распознается автоматом Бюхи (QА∪QB, Σ, ΔА∪ΔB, яА∪яB, FА∪FB).
  • Пересечение: Существует автомат Бюхи, распознающий язык L (A) ∩L (B).
Доказательство: Автомат Бюхи A '= (Q', Σ, ∆ ', I', F ') распознает L (A) ∩L (B), где
  • Q '=QА × QB × {1,2}
  • Δ '= Δ1 ∪ Δ2
    • Δ1 = {((qА, qB, 1), а, (q 'А, q 'B, i)) | (qА, а, q 'А) ∈ΔА и (qB, а, q 'B) ∈ΔB и если qА∈FА тогда i = 2 иначе i = 1}
    • Δ2 = {((qА, qB, 2), а, (q 'А, q 'B, i)) | (qА, а, q 'А) ∈ΔА и (qB, а, q 'B) ∈ΔB и если qB∈FB тогда i = 1 иначе i = 2}
  • Я '= ЯА × яB × {1}
  • F '= {(qА, qB, 2) | qB∈FB }
По построению r '= (qА0, qB0,я0), (qА1, qB1,я1), ... - запуск автомата A 'по входному слову ш если гА= qА0, qА1, ... запускается из A на ш и гB= qB0, qB1, ... выполняется из B на ш. рА принимает и гB принимается, если r 'является объединением бесконечной серии конечных сегментов 1-состояний (состояния с третьим компонентом 1) и 2-состояний (состояния с третьим компонентом 2) поочередно. Вот такая серия отрезков r ', если r' принимается A '.
  • Конкатенация: Существует автомат Бюхи, распознающий язык L (C) ⋅L (A).
Доказательство: Если предположить, w.l.o.g., QC∩QА пусто, то автомат Бюхи A '= (QC∪QА, Σ, Δ ', I', FА) распознает L (C) ⋅L (A), где
  • Δ '= ΔА ∪ ΔC ∪ {(q, a, q ') | q'∈IА и ∃f∈FC. (q, a, f) ∈∆C }
  • Если яC∩FC пусто, то I '= IC в противном случае I '= IC ∪ яА
  • ω-замыкание: Если L (C) не содержит пустого слова, то существует автомат Бюхи, распознающий язык L (C)ω.
Доказательство: Автомат Бюхи, распознающий L (C)ω строится в два этапа. Сначала мы построим конечный автомат A 'такой, что A' также распознает L (C), но нет входящих переходов в начальные состояния A '. Итак, A '= (QC ∪ {qновый}, Σ, Δ ', {qновый}, FC), где Δ '= ΔC ∪ {(qновый, a, q ') | ∃q∈IC. (q, a, q ') ∈∆C}. Обратите внимание, что L (C) = L (A '), потому что L (C) не содержит пустой строки. Во-вторых, мы построим автомат Бюхи A ", распознающий L (C)ω добавив петлю к исходному состоянию A '. Итак, A "= (QC ∪ {qновый}, Σ, Δ ", {qновый}, {qновый}), где Δ "= Δ '∪ {(q, a, qновый) | ∃q'∈FC. (q, a, q ') ∈∆'}.
  • Дополнение:Существует автомат Бюхи, распознающий язык Σω/ L (А).
Доказательство: Доказательство представлено здесь.

Узнаваемые языки

Автоматы Бюхи распознают ω-регулярные языки. Используя определение ω-регулярного языка и указанные выше свойства замыкания автоматов Бюхи, легко показать, что автомат Бюхи может быть построен так, что он распознает любой заданный ω-регулярный язык. Напротив, см. построение ω-регулярного языка для автомата Бюхи.

Детерминированные и недетерминированные автоматы Бюхи
Недетерминированный автомат Бюхи, распознающий (0∪1) * 0ω

Класса детерминированных автоматов Бюхи недостаточно для охвата всех омега-регулярных языков. В частности, не существует детерминированного автомата Бюхи, распознающего язык (0∪1) * 0ω, который содержит ровно слова, в которых 1 встречается только конечное число раз. Мы можем показать от противного, что такого детерминированного автомата Бюхи не существует. Ну допустим А является детерминированным автоматом Бюхи, распознающим (0∪1) * 0ω с установленным конечным состоянием F. А принимает 0ω. Так, А посетит какое-то государство в F после чтения некоторого конечного префикса 0ω, скажи после я0ое письмо. А также принимает ω-слово 0я010ω. Следовательно, для некоторых i1, после префикса 0я010я1 автомат посетит какое-то состояние в F. Продолжая эту конструкцию, ω-слово 0я010я110я2... генерируется, что заставляет A посетить некоторое состояние в F бесконечно часто и слово не находится в (0∪1) * 0ω. Противоречие.

Класс языков, распознаваемых детерминированными автоматами Бюхи, характеризуется следующей леммой.

Лемма: Ω-язык распознается детерминированным автоматом Бюхи, если он ограничить язык некоторых обычный язык.
Доказательство: Любой детерминированный автомат Бюхи A можно рассматривать как детерминированный конечный автомат A 'и наоборот, поскольку оба типа автоматов определены как набор из пяти одинаковых компонентов, различна только интерпретация условия приемки. Покажем, что L (A) - предельный язык L (A '). Ω-слово принимается A, если оно заставляет A посещать конечные состояния бесконечно часто. если бесконечно много конечных префиксов этого со-слова будет принимать А '. Следовательно, L (A) - предельный язык L (A ').

Алгоритмы

Проверка модели систем с конечным числом состояний часто можно преобразовать в различные операции над автоматами Бюхи. В дополнение к операциям замыкания, представленным выше, ниже приведены некоторые полезные операции для приложений автоматов Бюхи.

Детерминация

Поскольку детерминированные автоматы Бюхи строго менее выразительны, чем недетерминированные автоматы, не может быть алгоритма для детерминизации автоматов Бюхи. Теорема Макнотона и Строительство Сафры предоставить алгоритмы, которые могут преобразовать автомат Бюхи в детерминированный Автомат Мюллера или детерминированный Автомат Рабина.[2]

Проверка пустоты

Язык, распознаваемый автоматом Бюхи, непустой тогда и только тогда, когда существует конечное состояние, которое одновременно достижимо из начального состояния и лежит в цикле.

Эффективный алгоритм, который может проверить пустоту автомата Бюхи:

  1. Рассмотрим автомат как ориентированный граф и разложить на компоненты сильной связности (SCC).
  2. Выполните поиск (например, поиск в глубину ), чтобы определить, какие SCC достижимы из начального состояния.
  3. Проверьте, существует ли нетривиальный SCC, достижимый и содержащий конечное состояние.

Каждый из шагов этого алгоритма может быть выполнен за линейное время по размеру автомата, поэтому алгоритм явно оптимален.

Минимизация

Алгоритм для минимизация недетерминированного конечного автомата также правильно минимизирует автомат Бюхи. Алгоритм не гарантирует минимальный автомат Бюхи.[требуется разъяснение ].Однако алгоритмы для минимизация детерминированного конечного автомата не работает для детерминированного автомата Бюхи.

Варианты

Переход от других моделей описания к недетерминированным автоматам Бюхи

Из обобщенные автоматы Бюхи (GBA)
Несколько наборов состояний в условии принятия могут быть переведены в один набор состояний с помощью строительство автоматов, который известен как «счетная конструкция». Скажем А = (Q, Σ, ∆, q0, {F1, ..., Fп}) - GBA, где F1, ..., Fп являются множествами принимающих состояний, то эквивалентный автомат Бюхи А ' = (Q ', Σ, ∆', q '0, F '), где
  • Q '= Q × {1, ..., n}
  • q '0 = (q0,1 )
  • ∆ '= {((q, i), a, (q', j)) | (q, a, q ') ∈ ∆ и если q ∈ Fя тогда j = ((i + 1) mod n) else j = i}
  • F '= F1× {1}
Из Линейная временная логика формула
Дан перевод формулы линейной темпоральной логики на обобщенный автомат Бюхи. здесь. И перевод от обобщенного автомата Бюхи к автомату Бюхи представлен выше.
Из Автоматы Мюллера
Данный автомат Мюллера может быть преобразован в эквивалентный автомат Бюхи с помощью следующих строительство автоматов. Предположим А = (Q, Σ, ∆, Q0, {F0, ..., Fп}) - автомат Мюллера, где F0, ..., Fп представляют собой наборы принимающих состояний. Эквивалентный автомат Бюхи - это А ' = (Q ', Σ, ∆', Q0, F '), где
  • Q '= Q ∪ ∪пя = 0 {i} × Fя × 2Fя
  • ∆'= ∆ ∪ ∆1 ∪ ∆2, куда
    • ∆1 = {(q, a, (i, q ', ∅)) | (q, a, q ') ∈ ∆ и q' ∈ Fя }
    • ∆2= {((i, q, R), a, (i, q ', R')) | (q, a, q ') ∈∆ и q, q' ∈ Fя и если R = Fя тогда R '= ∅ иначе R' = R∪ {q}}
  • F '=∪пя = 0 {i} × Fя × {Fя}
А ' сохраняет исходный набор состояний из А и добавляет к ним дополнительные состояния. Автомат Бюхи А ' имитирует автомат Мюллера А следующим образом: В начале входного слова выполнение А ' следует за выполнением А, поскольку начальные состояния одинаковы и ∆ 'содержит ∆. В некоторой недетерминированно выбранной позиции во входном слове, А ' решает перейти в новые добавленные состояния через переход в ∆1. Тогда переходы в ∆2 постарайтесь посетить все штаты Fя и продолжай расти р. Один раз р становится равным Fя затем он сбрасывается в пустое множество и ∆2 постарайтесь посетить все штаты Fя заявляет снова и снова. Итак, если государства р=Fя посещаются бесконечно часто, тогда А ' принимает соответствующий ввод и делает то же самое А. Эта конструкция близко следует первой части доказательства Теорема Макнотона.
Из структур Крипке
Пусть данный Структура Крипке определяться M = <Q, я, р, L, AP> где Q это множество состояний, я - множество начальных состояний, р это отношение между двумя состояниями, также интерпретируемое как край, L это ярлык для государства и AP - набор атомарных предложений, которые образуютL.
Автомат Бюхи будет иметь следующие характеристики:
если (q, п) принадлежит р и L(п) = а
и инициализация q если q принадлежит я и L(q) = а.
Заметим, однако, что есть разница в интерпретации между структурами Крипке и автоматами Бюхи. В то время как первый явно называет полярность каждой переменной состояния для каждого состояния, последний просто объявляет текущий набор переменных, поддерживающих или не поддерживающих истину. Он абсолютно ничего не говорит о других переменных, которые могут присутствовать в модели.

Рекомендации

  1. ^ Бючи, Дж. Р. (1962). «О методе решения в ограниченной арифметике второго порядка». Proc. Международный конгресс по логике, методу и философии науки. 1960. Стэнфорд: Издательство Стэнфордского университета: 425–435. Дои:10.1007/978-1-4613-8928-6_23. ISBN  978-1-4613-8930-9.
  2. ^ Сафра, С. (1988), «О сложности ω-автоматов», Материалы 29-го ежегодного симпозиума по основам компьютерных наук (FOCS '88), Вашингтон, округ Колумбия, США: Компьютерное общество IEEE, стр. 319–327, Дои:10.1109 / SFCS.1988.21948, S2CID  206559211.

внешняя ссылка