Омега-регулярный язык

ω -регулярные языки — это класс ω-языков , которые обобщают определение регулярных языков на бесконечные слова.

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

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

• А ^ой где A — обычный язык, не содержащий пустой строки
• AB , объединение регулярного языка A и ω-регулярного языка B (обратите внимание, что BA является не четко определенным)
• A ∪ B , где A и B — ω-регулярные языки (это правило можно применять только конечное число раз)

Элементы А ^ой получаются путем объединения слов из А бесконечное число раз. Заметим, что если A регулярно, A ^ой не обязательно ω-регулярен, поскольку A может быть, например, {ε}, набором, содержащим только пустую строку , и в этом случае A ^ой = A , который не является ω-языком и, следовательно, не ω-регулярным языком.

Из определения следует, что ω-регулярные языки — это в точности ω-языки вида A ₁ B ₁ ^ой ∪ ... ∪ А _н Б _н ^ой для некоторого n , где A _и регулярными B _{являются} языками и не _B содержат пустую строку.

Эквивалентность автомату Бюхи

Теорема : ω-язык распознается автоматом Бюхи тогда и только тогда, когда он является ω-регулярным языком.

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

Обратно, для данного автомата Бюхи A = ( Q , Σ, δ, I , F ) затем покажем, что этот язык распознается A. мы построим ω-регулярный язык, а Для ω-слова w = a ₁ a ₂ ... пусть w ( i , j ) — конечный отрезок a _{i +1} ... a _{j -1} a _j слова w . Для каждого q , q' ∈ Q мы определяем регулярный язык L _q,q' , который принимается конечным автоматом ( Q , Σ, δ , q , { q' }) .

Лемма: Мы утверждаем, что автомат Бюхи A распознает язык ⋃ _{q ∈ I , q 'ε FL} q _,q' ( L _q',q' − { ε } ) ^ой .

Доказательство: предположим, что слово w ∈ L ( A ) и q ₀ , q ₁ , q ₂ ,... является принимающей серией A на w . Следовательно, q0 _q находится в I и должно существовать состояние q' в F такое, что ' встречается бесконечно часто в принимающей серии. Давайте выберем строго возрастающую бесконечную последовательность индексов i ₀ , i ₁ , i ₂ ... такую, что для всех k ≥0 q _{i k} равно q' . Следовательно, w (0, i ₀ )ε L _{q 0 , q'} и для всех k ≥0 w ( i _k , i _{k +1} )ε L _q',q' . Следовательно, w ∈ L _{q 0 ,q'} ( L _q',q' ) ^ой .

Обратно, предположим, что w ∈ L _q,q' ( L _q',q' − { ε } ) ^ой для некоторых q € I и q ' € F . Следовательно, существует бесконечная и строго возрастающая последовательность i ₀ , i ₁ , i ₂ ... такая, что w (0, i ₀ ) ∈ L _q,q' и для всех k ≥0 w ( i _k , i _{k +1} )ε L _q',q' . По определению L _q,q' существует конечная серия A от q до q' в слове w (0, i ₀ ). Для всех k ≥0 существует конечный пробег A от q' до q' в слове w ( i _k , i _{k +1} ). Согласно этой конструкции существует серия A , которая начинается с q и в которой q' встречается бесконечно часто. Следовательно, ш ∈ L ( А ) .

Эквивалентность монадической логике второго порядка

В 1962 году Бючи показал, что ω-регулярные языки — это именно те языки, которые можно определить в конкретной монадической логике второго порядка, называемой S1S.

Библиография

• Вольфганг Томас, «Автоматы на бесконечных объектах». , Ян ван Леувен редактор «Справочника по теоретической информатике», том B: Формальные модели и семантика , страницы 133–192. Издательство Elsevier Science, Амстердам, 1990.