ω-regular language

In theoretical computer science , the class of ω-regular languages denotes a certain set of formal languages made up of infinite words . The equivalent in the finite case is the regular language class .

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

The focus of the investigation of ω-regular languages ​​is on 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 . Above the alphabet can e.g. B. the infinite word can be formed. Sets of infinite words are called ω-languages. ${\displaystyle \{0,1\}}$ ${\displaystyle 0101111111\ldots }$

Formally this means:

Let be an alphabet, then the set of all infinite words above is defined as the set of all mappings from to . ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{\omega }}$ ${\displaystyle \Sigma }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \Sigma }$

Any subset of hot ω-language. ${\displaystyle \Sigma ^{\omega }}$

The ω-regular languages ​​now make up a certain subclass of the ω-languages.

definition

The ω-regular languages ​​are defined recursively . To do this, be a regular language that doesn't contain the empty word . Here denote the positive envelope of . ${\displaystyle U\subseteq \Sigma ^{+}}$ ${\displaystyle \Sigma ^{+}}$ ${\displaystyle \Sigma }$

Then the set of all countably infinite concatenations of words is from . ${\displaystyle U^{\omega }}$ ${\displaystyle U}$

The following applies now:

• ${\displaystyle U^{\omega }}$ is an ω-regular language.

In addition, let two ω-regular languages ​​be, then it also holds: ${\displaystyle L_{1};L_{2}}$

• ${\displaystyle U\circ L_{1},L_{1}\cup L_{2}}$and are also ω-regular languages. ${\displaystyle L_{1}\cap L_{2}}$

• Except for those constructed in this way, there are no ω-regular languages.

For the links used in the definition see also: Formal language # Operations on formal languages

literature

• Dominique Perrin, Jean-Éric Pin: Infinite Words Automata, Semigroups, Logic and Games (= Pure and Applied Mathematics. Vol. 141). Elsevier - Academic Press, Amsterdam et al. 2004, ISBN 0-12-532111-2 .
• Ludwig Staiger: ω-Languages . In: Grzegorz Rozenberg , Arto Salomaa (Ed.): Handbook of Formal Languages. Volume 3: Beyond Words. Springer, Berlin et al. 1997, ISBN 3-540-60649-1 , pp. 339-387.
• Wolfgang Thomas: Automata on Infinite Objects. In: Jan van Leeuwen (Ed.): Handbook of Theoretical Computer Science. Volume B: Formal Models and Semantics. Elsevier Science Publishers et al., Amsterdam et al. 1990, ISBN 0-444-88074-7 , pp. 133-192.