Омега-обычный язык
-
Определение Ω-регулярных языков
- Ω-регулярные языки обобщают обычные языки на бесконечное число слов.
- Ω-язык L является ω-регулярным, если он имеет вид Aw, где A — обычный язык без пустой строки.
- L может быть объединением обычного языка A и ω-обычного языка B, но BA не всегда определен.
- Элементы Aw получаются путем объединения слов бесконечно много раз.
-
Эквивалентность автомату Бюхи
- ω-язык распознается автоматом Бюхи тогда и только тогда, когда он является ω-обычным языком.
- Каждый ω-регулярный язык распознается недетерминированным автоматом Бюхи.
- Автомат Бюхи может быть построен для любого заданного ω-регулярного языка с использованием свойств замыкания и структурной индукции.
-
Эквивалентность монадической логике второго порядка
- В 1962 году Бюхи показал, что ω-регулярные языки определяются с помощью монадической логики второго порядка S1S.