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
Please cite the source for reprints, feel free to verify the sources cited in the article, and point out any errors or lack of clarity of expression. You can comment in the comments section below or email to GreenMeeple@yahoo.com