ω - регулярные языки — это класс ω-языков , которые обобщают определение регулярных языков на бесконечные слова. Бючи показал в 1962 году, что ω-регулярные языки — это именно те языки, которые можно определить в конкретной монадической логике второго порядка, называемой S1S.
Элементы A ω получаются конкатенацией слов из A бесконечное число раз. Обратите внимание, что если A регулярен, A ω не обязательно ω-регулярен, так как A может быть {ε}, множеством, содержащим только пустую строку , и в этом случае A ω = A , который не является ω-языком и, следовательно, не ω-регулярный язык.
Теорема : ω-язык распознается автоматом Бюхи тогда и только тогда, когда он является ω-регулярным языком.
Доказательство : каждый ω-регулярный язык распознается недетерминированным автоматом Бюхи; перевод конструктивный. Используя свойства замыкания автоматов Бюхи и структурную индукцию по определению ω-регулярного языка, можно легко показать, что автомат Бюхи может быть построен для любого заданного ω-регулярного языка.
Обратно, для данного автомата Бюхи 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' }) .