Омега-регулярный язык
ω -регулярные языки — это класс ω-языков , которые обобщают определение регулярных языков на бесконечные слова.
Формальное определение [ править ]
ω-язык L называется ω-регулярным, если он имеет вид
- А ой где A — обычный язык, не содержащий пустой строки
- AB , объединение регулярного языка A и ω-регулярного языка B (обратите внимание, что BA является не четко определенным)
- A ∪ B , где A и B — ω-регулярные языки (это правило можно применять только конечное число раз)
Элементы А ой получаются путем объединения слов из А бесконечное число раз.Заметим, что если A регулярно, A ой не обязательно ω-регулярен, поскольку A может быть, например, {ε}, набором, содержащим только пустую строку , и в этом случае A ой = A , который не является ω-языком и, следовательно, не ω-регулярным языком.
Из определения следует, что ω-регулярные языки — это в точности ω-языки вида A 1 B 1 ой ∪ ... ∪ А н Б н ой для некоторого n , где A i s и B i являются регулярными языками, а B i не содержат пустую строку.
автомату Эквивалентность Бюхи
Теорема : ω-язык распознается автоматом Бюхи тогда и только тогда, когда он является ω-регулярным языком.
Доказательство . Каждый ω-регулярный язык распознается недетерминированным автоматом Бюхи; перевод конструктивный. Используя свойства замыкания автоматов Бюхи и структурную индукцию по определению ω-регулярного языка, можно легко показать, что автомат Бюхи можно построить для любого данного ω-регулярного языка.
Обратно, для данного автомата Бюхи A = ( Q , Σ, δ, I , F ) затем покажем, что этот язык распознается A. мы построим ω-регулярный язык, а Для ω-слова w = a 1 a 2 ... пусть 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 0 , q 1 , q 2 ,... является принимающей серией A на w . Следовательно, q0 q находится в I , и должно существовать состояние q' в F такое, что ' встречается бесконечно часто в принимающей серии. Давайте выберем строго возрастающую бесконечную последовательность индексов i 0 , i 1 , i 2 ... такую, что для всех k ≥0 q i k равно q' . Следовательно, w (0, i 0 )ε 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 0 , i 1 , i 2 ... такая, что w (0, i 0 ) ∈ L q,q' и для всех k ≥0 w ( i k , i k +1 )ε L q',q' . По определению L q,q' существует конечная серия A от q до q' в слове w (0, i 0 ). Для всех k ≥0 существует конечный пробег A от q' до q' в слове w ( i k , i k +1 ). Согласно этой конструкции существует серия A , которая начинается с q и в которой q' встречается бесконечно часто. Следовательно, ш ∈ L ( А ) .
логике второго монадической Эквивалентность порядка
В 1962 году Бючи показал, что ω-регулярные языки — это именно те языки, которые можно определить в конкретной монадической логике второго порядка, называемой S1S.
Библиография [ править ]
- Вольфганг Томас, «Автоматы на бесконечных объектах». , Ян ван Леувен редактор «Справочника по теоретической информатике», том B: Формальные модели и семантика , страницы 133–192. Издательство Elsevier Science, Амстердам, 1990.