Теорема Макнотона - McNaughtons theorem - Wikipedia

В теория автоматов, Теорема Макнотона ссылается на теорему, которая утверждает, что множество ω-регулярные языки идентичен набору языков, распознаваемых детерминированными Автоматы Мюллера.^[1]Эта теорема доказывается предложением алгоритма построения детерминированного автомата Мюллера для любого ω-регулярного языка и наоборот.

Эта теорема имеет много важных следствий. Büchi автоматы а ω-регулярные языки столь же выразительный, из теоремы следует, что автоматы Бюхи и детерминированные автоматы Мюллера одинаково выразительны. Поскольку дополнение детерминированных автоматов Мюллера тривиально, из теоремы следует, что автоматы Бюхи / ω-регулярные языки замкнуты относительно дополняемости.

Оригинальное заявление

В оригинальной статье Макнотона теорема была сформулирована следующим образом:

«Ω-событие является регулярным тогда и только тогда, когда оно является конечным».

В современной терминологии ω-события обычно называют ω-языки. Следуя определению Макнотона, ω-событие - это конечное событие если существует детерминированный автомат Мюллера, который его распознает.

Построение ω-регулярного языка из детерминированного автомата Мюллера

Одно направление теоремы может быть доказано, если показать, что любой данный автомат Мюллера распознает ω-регулярный язык.

Предполагать А = (Q, Σ, δ,q₀,F) является детерминированным Автомат Мюллера. Объединение конечного числа ω-регулярных языков дает ω-регулярный язык, поэтому можно считать, что w.l.o.g. что условие принятия Мюллера F содержит ровно один набор состояний {q₁, ..., q_п}. Пусть α - обычный язык чьи элементы возьмут А из q₀ к q₁. Для 1≤i≤n пусть β_я быть регулярным языком, элементы которого принимают А из q_я к q_{(я мод п) +1} не проходя через какое-либо состояние вне {q₁, ..., q_п}. Утверждается, что α (β₁ ... β_п)^ω является ω-регулярным языком, распознаваемым автоматом Мюллера А. Это доказывается следующим образом.

Предполагать ш это слово принято А. Пусть ρ - пробег, который привел к принятию ш. Для момента времени t пусть ρ (t) будет состоянием, которое посетил ρ в момент t. Создадим бесконечную и строго возрастающую последовательность моментов времени t₁, т₂, ... такие, что для любых a и b ρ (t_{na + b}) = q_б. Такая последовательность существует, поскольку все состояния {q₁, ..., q_п} появляются в ρ бесконечно часто. С помощью приведенных выше определений α и β легко показать, что из существования такой последовательности следует, что ш является элементом α (β₁ ... β_п)^ω.

Предполагать ш ∈ α (β₁ ... β_п)^ω. По определению α существует начальный участок ш который является элементом α и приводит А государству q₁. С этого момента запуск никогда не перейдет в состояние, отличное от {q₁, ..., q_п} из-за определений β, и все состояния в наборе повторяются бесконечно часто. Следовательно, А принимает слово ш.

Построение детерминированного автомата Мюллера по заданному ω-регулярному языку

Другое направление теоремы можно доказать, показав, что существует автомат Мюллера, распознающий данный ω-регулярный язык.

Объединение конечного числа детерминированных автоматов Мюллера может быть легко построено, поэтому w.l.o.g. мы предполагаем, что данный ω-регулярный язык имеет вид αβ^ω. Предположим ω-слово ш= а₁, а₂, ... ∈ αβ^ω. Позволять ш(i, j) - конечный отрезок a_{я + 1}, ..., а_j-1, а_j из w. Для построения автомата Мюллера для αβ^ω, введем следующие два понятия относительно ш.

Услуга

Время j благосклонность время i, если j> i, ш(0, i) ∈ αβ * и ш(i, j) ∈ β *.

Эквивалентность

E (я, j, k), или я эквивалент к j как судили в момент k, если i, j ≤ k, ш(0, i) ∈ αβ *,ш(0, j) ∈ αβ *, и для каждого слова x из Σ * ш(i, k) x ∈ β * тогда и только тогда, когда ш(j, k) x ∈ β *. Легко заметить, что если E (i, j, k), то для всех k E (i, j) если существует k такое, что E (i, j, k).

Пусть p - количество состояний в минимуме детерминированный конечный автомат А^{β *} распознавать язык β *. Теперь докажем две леммы о двух указанных выше понятиях.

Лемма 1.

Для любого момента времени k среди моментов времени i, j

Доказательство: Конечный автомат A^{β *} минимально поэтому не содержит эквивалентные состояния. Пусть i и j таковы, что ш(0, i) и ш(0, j) ∈ αβ * и E (i, j, k). Затем слова ш(i, k) и ш(j, k) должен будет взять A^{β *} в такое же состояние, начиная с начального состояния. Следовательно, первая часть леммы верна. Вторая часть доказывается от противного. Предположим, что имеется p + 1 умноженное на i₁,...,я_{п + 1} такие, что никакие два из них не эквивалентны. Для l> max (i₁,...,я_{п + 1}), для каждого m и n мы бы имели не E (i_м,я_п, л). Следовательно, было бы p + 1 классов эквивалентности, как следует из пункта l, что противоречит первой части леммы.

Лемма 2

w ∈ αβ^ω если и только если существует такое время i, что существует бесконечно много раз, эквивалентных i и благоприятствующих i.

Доказательство: Предположим, что w ∈ αβ^ω то существует строго возрастающая последовательность времен i₀,я₁,я₂, ... такие, что w (0, i₀) ∈ α и w (i_п,я_{п + 1}) ∈ β. Следовательно, для всех n> m w (i_м,я_п) ∈ β * и i_п благоволит мне_м. Итак, все i являются членами одного из конечного числа классов эквивалентности (показанных в лемме 1). Итак, должно быть бесконечное подмножество всех i, принадлежащих к одному классу. Наименьший член этого подмножества удовлетворяет правой части этой леммы.

Наоборот, предположим, что в w бесконечно много раз эквивалентны i и благоприятствуют i. С тех пор мы построим строго возрастающую и бесконечную последовательность времен i₀,я₁,я₂, ... такие, что w (0, i₀) ∈ αβ * и w (i_п,я_{п + 1}) ∈ β *, следовательно, w было бы в αβ^ω. Определим эту последовательность по индукции:

Базовый вариант: w (0, i) ∈ αβ *, поскольку i находится в классе эквивалентности. Итак, мы устанавливаем i₀= я. Мы устанавливаем я₁ так что я₁ благоволит мне₀ и E (i₀,я₁). Итак, w (i₀,я₁) ∈ β *.

Индукционный шаг: Предположим, что E (i₀,я_п). Итак, существует время i 'такое, что E (i₀,я_п,я'). Мы устанавливаем я_{п + 1} так что я_{п + 1} > я ', я_{п + 1} благоволит мне₀, а E (i₀,я_{п + 1}). Итак, w (i₀,я_{п + 1}) ∈ β * и, поскольку i_{п + 1} > i 'по определению E (i₀,я_п, i '), w (i_п,я_{п + 1}) ∈ β *.

Конструкция автомата Мюллера

В лемме 2 мы использовали понятия «благосклонности» и «эквивалентности». Теперь мы собираемся использовать лемму для строить автомат Мюллера для языка αβ^ω. Предлагаемый автомат примет слово тогда и только тогда, когда существует время i такое, что оно удовлетворяет правой части леммы 2. Машина ниже описывается неформально. Обратите внимание, что эта машина будет детерминированным автоматом Мюллера.

Машина содержит p + 2 детерминированного конечного автомата и мастер-контроллер, где p - размер A^{β *}. Одна из машин p + 2 может распознать αβ *, и эта машина получает ввод в каждом цикле. И он в любое время связывается с главным контроллером независимо от того, ш(0, i) ∈ αβ *. Остальные p + 1 машины являются копиями A^{β *}. Мастер может установить A^{β *} машины бездействующие или активные. Если мастер устанавливает A^{β *} машина бездействует, тогда она остается в своем исходном состоянии и не обращает внимания на ввод. Если мастер активирует A^{β *} затем машина считывает ввод и перемещается, пока мастер не сделает его бездействующим и не вернет его в исходное состояние. Мастер может сделать пятёрку^{β *} машина активна и бездействует сколько угодно раз. Мастер хранит следующую информацию о A^{β *} машины в каждый момент времени.

• Текущее состояние A^{β *} машины.
• Список активных A^{β *} машины в порядке их активации.
• Для каждого активного A^{β *} машина M, множество других активных A^{β *} машины, которые находились в состоянии приема во время активации M. Другими словами, если машина стала активной в момент времени i, а какая-то другая машина была в последний раз активна в j

Первоначально мастер может вести себя двумя разными способами в зависимости от α. Если α содержит пустое слово, то только одно из A^{β *} активен, иначе ни один из A^{β *} машины активны на старте. Позже в какой-то момент i, если w (0, i) ∈ αβ * и ни одно из A^{β *} машины находятся в исходном состоянии, тогда мастер активирует одну из бездействующих машин, и только что активированный A^{β *} машина начинает получать ввод с момента i + 1. В какой-то момент, если два A^{β *} машины достигают того же состояния, тогда мастер переводит машину в неактивное состояние, которая была активирована позже, чем другая. Обратите внимание, что мастер может принимать вышеуказанные решения, используя информацию, которую он хранит.

Для выхода у мастера также есть пара красных и зеленых огней, соответствующих каждому A^{β *} машина. Если A^{β *} машина переходит из активного состояния в неактивное, затем мигает соответствующий красный свет. Зеленый свет для некоторых A^{β *} машина M, которая была активирована в j, мигает в момент i в следующих двух ситуациях:

• M находится в начальном состоянии, таким образом, E (j, i, i) и i благоприятствует j (начальное состояние должно быть состоянием принятия).
• Для некоторых других активных A^{β *} машина M 'активирована в k, где j

Обратите внимание, что зеленый свет для M не мигает каждый раз, когда машина переходит в неактивное состояние из-за M.

Лемма 3.

Если существует время, эквивалентное бесконечному числу раз, которое благоприятствует этому, и i - самое раннее такое время, то A^{β *} машина M активируется в i, остается активной навсегда (после этого не мигает соответствующий красный свет) и мигает зеленым светом бесконечно много раз.

Доказательство: Предположим, что A^{β *} машина была активирована в момент j, так что j β * машина в момент времени i, которая является нашим M. Эта машина никогда не перейдет в спящий режим, потому что если какая-то другая машина, которая была активирована в момент l, сделает ее бездействующей в момент времени k, то E (l, i, k). Снова подразумевается то же противоречие. По конструкции и из-за того, что бесконечно много раз эквивалентны i и благосклонно i, зеленый свет будет мигать бесконечно часто.

Лемма 4.

Наоборот, если существует A^{β *} машина M, зеленый свет которой мигает бесконечно часто, а красный - только конечное часто, то есть бесконечно много раз, эквивалентных и благоприятствующих последнему моменту, когда M.

Доказательство: Верно по конструкции.

Лемма 5.

w ∈ αβ^ω если и только тогда, для некоторого A^{β *} машины зеленый индикатор мигает бесконечно часто, а красный индикатор мигает очень часто.

Доказательство: По лемме 2-4.

Приведенное выше описание полной машины можно рассматривать как большой детерминированный автомат. Теперь осталось определить условие приемки Мюллера. В этом большом автомате определим μ_п быть набором состояний, в которых зеленый свет мигает, а красный свет не мигает, что соответствует n^th А^{β *} машина. Пусть ν_п - набор состояний, в которых красный свет не мигает, соответствующий n^th А^{β *} машина. Итак, условие приемки Мюллера F = {S | ∃n μ_п ⊆ S ⊆ ν_п }. Это завершает построение желаемого автомата Мюллера. Q.E.D.

Прочие доказательства

После доказательства Макнотона было предложено много других доказательств. Ниже приведены некоторые из них.

• ω-регулярный язык можно показать эквивалентным Büchi автоматы. Можно показать, что автоматы Бюхи эквивалентны полудетерминированные автоматы Бюхи. Можно показать, что полудетерминированные автоматы Бюхи эквивалентны детерминированным автоматам Мюллера. Это доказательство следует тем же принципам, что и предыдущее.
• Строительство Сафры преобразует недетерминированный автомат Бюхи в автомат Рабина.^[2] Эта конструкция известна как оптимальная.
• Есть чисто алгебраическое доказательство^[3] теоремы Макнотона.

Список литературы

1. Макнотон, Р .: "Тестирование и создание бесконечных последовательностей с помощью конечного автомата", Информация и контроль 9, стр. 521–530, 1966.
2. Сафра, С. (1988), «О сложности ω-автоматов», Материалы 29-го ежегодного Симпозиум по основам информатики (FOCS '88), Вашингтон, округ Колумбия, США: IEEE Computer Society, стр. 319–327, Дои:10.1109 / SFCS.1988.21948.
3. Б. Ле Саек, Ж. Пин, П. Вейль, Чисто алгебраическое доказательство теоремы Макнотона о бесконечных словах, Основы программных технологий и теоретической информатики, п. 141–151