Büchi автомат - Büchi automaton

Автомат Бюхи с двумя состояниями, ${\displaystyle q_{0}}$ и ${\displaystyle q_{1}}$, первое из которых является начальным, а второе - принимающим. Его входные данные - бесконечные слова над символами ${\displaystyle \{a,b\}}$. Например, он принимает бесконечное слово ${\displaystyle (ab)^{\omega }}$, куда ${\displaystyle x^{\omega }}$ обозначает бесконечное повторение строки. Он отвергает бесконечное слово ${\displaystyle aaab^{\omega }}$.

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

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

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

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

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

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

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

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

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

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

Пусть A = (Q_А, Σ, Δ_А,я_А,F_А) и B = (Q_B, Σ, Δ_B,я_B,F_B) - автоматы Бюхи и C = (Q_C, Σ, Δ_C,я_C,F_C) быть конечный автомат.

• Союз: Существует автомат Бюхи, распознающий язык L (A) ∪L (B).

Доказательство: Если предположить, w.l.o.g., Q_А∩Q_B пусто, то L (A) ∪L (B) распознается автоматом Бюхи (Q_А∪Q_B, Σ, Δ_А∪Δ_B, я_А∪я_B, F_А∪F_B).

• Пересечение: Существует автомат Бюхи, распознающий язык L (A) ∩L (B).

Доказательство: Автомат Бюхи A '= (Q', Σ, ∆ ', I', F ') распознает L (A) ∩L (B), где

• Q '=Q_А × Q_B × {1,2}
• Δ '= Δ₁ ∪ Δ₂
  • Δ₁ = {((q_А, q_B, 1), а, (q '_А, q '_B, i)) | (q_А, а, q '_А) ∈Δ_А и (q_B, а, q '_B) ∈Δ_B и если q_А∈F_А тогда i = 2 иначе i = 1}
  • Δ₂ = {((q_А, q_B, 2), а, (q '_А, q '_B, i)) | (q_А, а, q '_А) ∈Δ_А и (q_B, а, q '_B) ∈Δ_B и если q_B∈F_B тогда i = 1 иначе i = 2}
• Я '= Я_А × я_B × {1}
• F '= {(q_А, q_B, 2) | q_B∈F_B }

По построению r '= (q_А⁰, q_B⁰,я⁰), (q_А¹, q_B¹,я¹), ... - запуск автомата A 'по входному слову ш если г_А= q_А⁰, q_А¹, ... запускается из A на ш и г_B= q_B⁰, q_B¹, ... выполняется из B на ш. р_А принимает и г_B принимается, если r 'является объединением бесконечной серии конечных сегментов 1-состояний (состояния с третьим компонентом 1) и 2-состояний (состояния с третьим компонентом 2) поочередно. Вот такая серия отрезков r ', если r' принимается A '.

• Конкатенация: Существует автомат Бюхи, распознающий язык L (C) ⋅L (A).

Доказательство: Если предположить, w.l.o.g., Q_C∩Q_А пусто, то автомат Бюхи A '= (Q_C∪Q_А, Σ, Δ ', I', F_А) распознает L (C) ⋅L (A), где

• Δ '= Δ_А ∪ Δ_C ∪ {(q, a, q ') | q'∈I_А и ∃f∈F_C. (q, a, f) ∈∆_C }
• Если я_C∩F_C пусто, то I '= I_C в противном случае I '= I_C ∪ я_А

• ω-замыкание: Если L (C) не содержит пустого слова, то существует автомат Бюхи, распознающий язык L (C)^ω.

Доказательство: Автомат Бюхи, распознающий L (C)^ω строится в два этапа. Сначала мы построим конечный автомат A 'такой, что A' также распознает L (C), но нет входящих переходов в начальные состояния A '. Итак, A '= (Q_C ∪ {q_новый}, Σ, Δ ', {q_новый}, F_C), где Δ '= Δ_C ∪ {(q_новый, a, q ') | ∃q∈I_C. (q, a, q ') ∈∆_C}. Обратите внимание, что L (C) = L (A '), потому что L (C) не содержит пустой строки. Во-вторых, мы построим автомат Бюхи A ", распознающий L (C)^ω добавив петлю к исходному состоянию A '. Итак, A "= (Q_C ∪ {q_новый}, Σ, Δ ", {q_новый}, {q_новый}), где Δ "= Δ '∪ {(q, a, q_новый) | ∃q'∈F_C. (q, a, q ') ∈∆'}.

• Дополнение:Существует автомат Бюхи, распознающий язык Σ^ω/ L (А).

Доказательство: Доказательство представлено здесь.

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

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

Детерминированные и недетерминированные автоматы Бюхи

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

Класса детерминированных автоматов Бюхи недостаточно для охвата всех омега-регулярных языков. В частности, не существует детерминированного автомата Бюхи, распознающего язык (0∪1) * 0^ω, который содержит ровно слова, в которых 1 встречается только конечное число раз. Мы можем показать от противного, что такого детерминированного автомата Бюхи не существует. Ну допустим А является детерминированным автоматом Бюхи, распознающим (0∪1) * 0^ω с установленным конечным состоянием F. А принимает 0^ω. Так, А посетит какое-то государство в F после чтения некоторого конечного префикса 0^ω, скажи после я₀ое письмо. А также принимает ω-слово 0^я₀10^ω. Следовательно, для некоторых i₁, после префикса 0^я₀10^я₁ автомат посетит какое-то состояние в F. Продолжая эту конструкцию, ω-слово 0^я₀10^я₁10^я₂... генерируется, что заставляет 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, Σ, ∆, q₀, {F₁, ..., F_п}) - GBA, где F₁, ..., F_п являются множествами принимающих состояний, то эквивалентный автомат Бюхи А ' = (Q ', Σ, ∆', q '₀, F '), где

• Q '= Q × {1, ..., n}
• q '₀ = (q₀,1 )
• ∆ '= {((q, i), a, (q', j)) | (q, a, q ') ∈ ∆ и если q ∈ F_я тогда j = ((i + 1) mod n) else j = i}
• F '= F₁× {1}

Из Линейная временная логика формула

Дан перевод формулы линейной темпоральной логики на обобщенный автомат Бюхи. здесь. И перевод от обобщенного автомата Бюхи к автомату Бюхи представлен выше.

Из Автоматы Мюллера

Данный автомат Мюллера может быть преобразован в эквивалентный автомат Бюхи с помощью следующих строительство автоматов. Предположим А = (Q, Σ, ∆, Q₀, {F₀, ..., F_п}) - автомат Мюллера, где F₀, ..., F_п представляют собой наборы принимающих состояний. Эквивалентный автомат Бюхи - это А ' = (Q ', Σ, ∆', Q₀, F '), где

• Q '= Q ∪ ∪^п_{я = 0} {i} × F_я × 2^F_я
• ∆'= ∆ ∪ ∆₁ ∪ ∆₂, куда
  • ∆₁ = {(q, a, (i, q ', ∅)) | (q, a, q ') ∈ ∆ и q' ∈ F_я }
  • ∆₂= {((i, q, R), a, (i, q ', R')) | (q, a, q ') ∈∆ и q, q' ∈ F_я и если R = F_я тогда R '= ∅ иначе R' = R∪ {q}}
• F '=∪^п_{я = 0} {i} × F_я × {F_я}

А ' сохраняет исходный набор состояний из А и добавляет к ним дополнительные состояния. Автомат Бюхи А ' имитирует автомат Мюллера А следующим образом: В начале входного слова выполнение А ' следует за выполнением А, поскольку начальные состояния одинаковы и ∆ 'содержит ∆. В некоторой недетерминированно выбранной позиции во входном слове, А ' решает перейти в новые добавленные состояния через переход в ∆₁. Тогда переходы в ∆₂ постарайтесь посетить все штаты F_я и продолжай расти р. Один раз р становится равным F_я затем он сбрасывается в пустое множество и ∆₂ постарайтесь посетить все штаты F_я заявляет снова и снова. Итак, если государства р=F_я посещаются бесконечно часто, тогда А ' принимает соответствующий ввод и делает то же самое А. Эта конструкция близко следует первой части доказательства Теорема Макнотона.

Из структур Крипке

Пусть данный Структура Крипке определяться M = <Q, я, р, L, AP> где Q это множество состояний, я - множество начальных состояний, р это отношение между двумя состояниями, также интерпретируемое как край, L это ярлык для государства и AP - набор атомарных предложений, которые образуютL.

Автомат Бюхи будет иметь следующие характеристики:

${\displaystyle Q_{\text{final}}=Q\cup \{{\text{init}}\}}$

${\displaystyle \Sigma =2^{AP}}$

${\displaystyle I=\{{\text{init}}\}}$

${\displaystyle F=Q\cup \{{\text{init}}\}}$

${\displaystyle \delta =q{\overrightarrow {a}}p}$ если (q, п) принадлежит р и L(п) = а

и инициализация ${\displaystyle {\overrightarrow {a}}}$ 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.

• Бахадыр Хусаинов; Анил Нероде (6 декабря 2012 г.). Теория автоматов и ее приложения. Springer Science & Business Media. ISBN  978-1-4612-0171-7.
• Томас, Вольфганг (1990). «Автоматы на бесконечных объектах». В Ван Левен (ред.). Справочник по теоретической информатике. Эльзевир. С. 133–164.

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

• «Конечные автоматы на бесконечных входах» (PDF).
• Варди, Моше Ю. "Теоретико-автоматный подход к линейной темпоральной логике". CiteSeerX  10.1.1.125.8126.