Omega-regular language

In theoretical computer science, the class of ω - regular languages ​​denoted a certain amount of formal languages ​​of infinite words. The equivalent in the finite case is the class of regular languages ​​.

The Greek letter ω ( omega) stands for the smallest infinite ordinal.

The focus of the study ω - regular languages ​​lies in automata theory. It can be shown, for example, that the ω - regular languages ​​are exactly the Büchi recognizable languages.

Infinite words

An infinite word is a countably infinite sequence of characters from a finite alphabet. Via the alphabet, for example, the infinite word can be formed. Sets of infinite words are called ω - languages.

Formally, this means:

Be an alphabet, then the set of all infinite words is defined as the set of all functions from to.

Every subset of hot ω - language.

The ω - regular languages ​​now account for a certain subclass of ω - languages.

Definition

The definition of ω - regular languages ​​is recursive. For this purpose let a regular language that does not contain the empty word. The positive hull of call.

Then, from the set of all countably infinite concatenations of words.

It now applies:

• Is an ω - regular language.

Also be two ω - regular languages ​​, then still applies:

• And are also ω - regular languages ​​.

• In addition to the thus constructed, there is no ω - regular languages ​​.

For the links used in the definition see also: Formal Language # operations on formal languages

• Theory of formal languages