Теорема МакНотона - Википедия - McNaughtons theorem

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Теорема Макнотона»  – Новости  · газеты  · книги  · ученый  · JSTOR (Август 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

В теория автоматов, Теорема Макнотона ссылается на теорему, которая утверждает, что множество ω-регулярные языки идентичен набору языков, распознаваемых детерминированными Автоматы Мюллера.^[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.

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