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

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

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

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

  • A ω, где A - непустой регулярный язык, не содержащий пустой строки
  • АВ , конкатенация обычного языка A и ω-регулярный язык Б (Обратите внимание , что БА является не хорошо определена)
  • A ∪ B, где A и B - ω-регулярные языки (это правило можно применять только конечное число раз)

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

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

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

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

С другой стороны , для данного автомата Бюхи A  = ( Q , Σ, δ, I , F ), мы строим со-регулярный язык , а затем покажем , что этот язык признан A . Для со-словом ш = с 1 на 2 ... пусть ш ( я , J ) будет конечным отрезком я +1 ... ямайские -1 ямайские из ж . Для каждого q , q ' ∈ Q определим регулярный язык L q, q', который принимается конечным автоматом ( Q , Σ, δ, q , {q '}).

Лемма: Мы утверждаем, что автомат Бюхи A распознает язык ⋃ q∈ I , q'∈ F   L q, q '  ( L q', q ' - {ε}) ω .
Доказательство. Предположим, что слово w  ∈  L (A) и q 0 , q 1 , q 2 , ... является принимающим пробегом A на w . Следовательно, q 0 находится в I, и должно быть состояние q 'в F такое, что q' встречается бесконечно часто в принимающем прогоне. Выберем возрастающую бесконечную последовательность индексов 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 '  ) ω .
Теперь предположим, что ж  ∈  L д, д '  ( L д', д» - {ε}) ω для некоторого 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 'встречается бесконечно часто. Следовательно, w  ∈  L (A) .

Список используемой литературы

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