AGV 3.2 -- $\omega$-regular language

Previous chapter: Kleene’s Theorem

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

Introduction

$\omega$-regular expression denotes languages over infinite words.
In addition to language union on languages over infinite words, we have 2 operations that convert languages over finite words into languages over infinite words.

$\omega$-regular expression

The collection of $\omega$-regular languages over an alphabet $\Sigma^\omega$ is $\mathcal{L}(W)$, where $W$ is a $\omega$-regular expression.
$\omega$-regular expression can be defined as $W := E^\omega \mid E\cdot W\mid W_1+W_2 $, where:

• infinite concatenation of a non-empty regular language $E^\omega$,
• union of $\omega$-regular languages, $W_1+W_2$, and
• concatenation of regular languages and $\omega$-regular language $E\cdot W$

$\textbf{Definition 3.3. } \textit{$\omega$-Regular expressions } \text{are defined as follows:}$
$\begin{array}{l}
\hspace{1cm} \cdot \ \text{If $E$ is a regular expression where $\varepsilon\notin\mathcal{L}(E)$, then $E^\omega$ is an $\omega$-regular expression.}\newline
\hspace{1cm} \ \ \mathcal{L}(E^\omega) = \mathcal{L}(E)^\omega\newline
\hspace{1cm} \ \ \text{where } L^\omega =\lbrace \omega_0\omega_1\dots\mid\omega_i\in L,|\omega_i|>0\rbrace \text{ for } L\subseteq\Sigma^* \newline
\hspace{1cm} \cdot \ \text{If $E$ is a regular expression and $W$ is an $\omega$-regular expression,}\newline
\hspace{1cm} \ \ \text{then $E\cdot W$ is an $\omega$-regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(E\cdot W) = \mathcal{L}(E)\cdot\mathcal{L}(W)\newline
\hspace{1cm} \ \ \text{where } L_1 \cdot L_2=\lbrace \omega\alpha\mid\omega\in L_1,\alpha\in L_2\rbrace \text{ for } L_1 \subseteq\Sigma^*, L_2 \subseteq\Sigma^\omega\newline
\hspace{1cm} \cdot \ \text{If $W_1$ and $W_2$ are $\omega$-regular expressions, then $W_1+W_2$ is an $\omega$-regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(W_1+W_2) = \mathcal{L}(W_1)\cup\mathcal{L}(W_2) .\newline
\end{array}$

A language over infinite words is $\omega$-regular if it is definable by a $\omega$-regular expression.

---

Next chapter: Closure Properties of the Büchi-recognizable languages (Intersection and Union)

Further Reading: Omega language, Omega Regular language, Büchi automaton