Previous chapter: Büchi’s Characterization Theorem
This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner
Introduction
In the theory of automata over finite words, we have Rabin-Scott powerset construction, which converts a nondeterministic automaton over finite words into a deterministic automaton that recognizes the same language. This shows that nondeterminism does not make automata over finite words more expressive (but makes it more concise as the construction produces an exponential number of states).
The situation is different for Büchi automata: even though the language $L = (a+b)^*b^\omega$ is clearly Büchi-recognizable, there is, as the following theorem shows, no deterministic Büchi automaton that recognizes L.
Deterministic vs. nondeterministic Büchi automata
$\textbf{Theorem 4.1. }\textit{Language $L=(a+b)^*b^\omega$ is not recognizable by deterministic Büchi Automata}$
Starting a base case $b^\omega$, we add $(a+b)$ as the prefix one by one. Can we express the kleene star?
That is, is the automaton only accept finitely many $(a+b)$?
Proof
Assume, by way of contradiction, that $L$ is recognizable by the deterministic Büchi automaton $\mathcal{A}=(\Sigma,Q,I,T,\small\text{BÜCHI}\normalsize(F))$. Since $\alpha_0=b^\omega$ is in $L$, there is an unique run
$$r_0=r_0(0)r_0(1)r_0(2)\dots$$
of $\mathcal{A}$ on $\alpha_0$ with $r_0(n_0)\in F$ for some $n_0\in\mathbb{N}$. Similarly, $\alpha_1=b^{n_0}ab^\omega$ in $L$ and there is a unique run
$$r_1=r_0(0)r_0(1)r_0(2)\dots r_0(n_0)r_1(n_0+1)r_1(n_0+2)\dots$$
of $\mathcal{A}$ on $\alpha_1$ with $r_1(n_1)\in F$ for some $n_1>n_0$. Since $\mathcal{A}$ is deterministic, $r_0$ & $r_1$ are identical up to position $n_0$.
By repeating this argument infinitely often, we obtain a word $\alpha=b^{n_0}ab^{n_1}ab^{n_2}a\dots$ and a run $r$ with infinitely many visits to $F$. Hence, $\alpha$ is accepted by $\mathcal{A}$. However, $\alpha$ is not an element of $L$. This contradicts $L = \mathcal{L}(\mathcal{A})$.
Limit Operator
We start by defining a Limit Operator to generate $\omega$-language using regular language. For the regular language $W$, $\overrightarrow{W}$ contains all the words that they all contain words in $W$ as substrings.
$\textbf{Definition 4.1. }\text{(Limit). The}\textit{ limit }\overrightarrow{W}\text{ of a language }W\subseteq\Sigma^* \text{ over finite words}\newline\text{is the following language over infinite words:}$ $$\overrightarrow{W}=\lbrace\alpha\in\Sigma^\omega\mid\text{there exist infinitely many }n\in\mathbb{N}\text{ s.t. }\alpha[0,n]\in W\rbrace.$$
And From regular language, now we can define an $\omega$-regular language that is recognizable by deterministic Büchi Automata:
$\textbf{Theorem 4.2. }\textit{An $\omega$-language $L\subseteq\Sigma^\omega$ is recognizable by a deterministic Büchi Automata}\newline\textit{iff there is a regular langauge $W\subseteq\Sigma^*$ s.t. $L=\overrightarrow{W}$}.$
Explained in Human language
Basically, we are trying to prove $\mathcal{L}(\mathcal{A_B})=\overrightarrow{\mathcal{L}(\mathcal{A_F})}$, where $\mathcal{L}(\mathcal{A_B})$ is a deterministic Büchi Automata and $\mathcal{L}(\mathcal{A_F})$ is a a deterministic automaton over finite words.
As we can see, an accepted word $\alpha\in\mathcal{L}(\mathcal{A_B})$ with have substring $\alpha[0,n]$ that is accepted by $\mathcal{L}(\mathcal{A_F})$ with infinitely many $n\in\mathbb{N}$, by the definition of the limit operator.
We can prove regular language $W$ exists if $\alpha$ exists using $\overrightarrow{W}$. Automata that accepts $W$ and $\overrightarrow{W}$ should exist, namely $\mathcal{L}(\mathcal{A_F})$ and $\overrightarrow{\mathcal{L}(\mathcal{A_F})}$ respectively.
Formal Proof
We claim that the languages of a deterministic Büchi automaton $\mathcal{A}_B$ and of a deterministic
automaton over finite words $\mathcal{A}_F$, where the automata $\mathcal{A}_B=(\Sigma,Q,I,T,\small\text{BÜCHI}\normalsize(F))$ and $\mathcal{A}_F=(\Sigma,Q,I,T,F)$, constructed from the same components, are related as follows:
$$\mathcal{L}(\mathcal{A_B})=\overrightarrow{\mathcal{L}(\mathcal{A_F})}.$$
Since every regular language is recognized by a deterministic automaton over finite words,
the theorem follows. To prove the claim, we consider an infinite word $\alpha\in\Sigma^\omega$.
$\hspace{1cm}\alpha\in\mathcal{L}(\mathcal{A_B})\newline
\text{iff} \hspace{0.5cm}\text{for the unique run $r$ of $\mathcal{A_B}$ on $\alpha$, Inf($r$) $\cap$ $F\neq\varnothing$}\newline \text{iff} \hspace{0.5cm} \alpha[0,n]\in\mathcal{L}(\mathcal{A_F})\text{ for infinitely many }n\in\mathbb{N}\newline
\text{iff} \hspace{0.5cm} \alpha\in\mathcal{L}(\mathcal{A_F})$
Next chapter: Complementation of deterministic Büchi Automata
Further Reading: powerset construction
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