Previous chapter: Closure Properties of the Büchi-recognizable languages (Intersection and Union)
This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner
In this section, we continue the proof of the closure properties of the Büchi-recognizable languages.
Concatenation of regular Langauge and Büchi-recognizable Language
$\textbf{Construction 3.3. } \text{Let }\mathcal{A}_1=(\Sigma,Q_1,I_1,T_1,F_1)\text{ be an automaton over finite words that}\newline\text{recognizes the languge }L_1\text{, and let }\mathcal{A}_2 = (\Sigma,Q_2,I_2,T_2,\small\text{BÜCHI}\normalsize (F_2))\text{ be a Büchi automaton}\newline\text{over the same alphabet that recognizes }L_2.\text{ We construct a Büchi autotmaton }\newline\mathcal{A’}=(\Sigma,Q’,I’,T’,\small\text{BÜCHI}\normalsize (F_2))\text{ with }\mathcal{L}(\mathcal{A’})=L_1\cdot L_2\text{ as follows:}$
$\begin{array}{lrll}
\hspace{1cm} \cdot &Q’&=&Q_1\cup Q_2 \hspace{0.7cm}(\text{w.l.o.g we assume }Q_1\cap Q_2=\varnothing)\newline
\hspace{1cm} \cdot &I’&=&\biggl\lbrace \begin{array}{ll}I_1 & \ \text{if }I_1\cap F_1=\varnothing\newline
I_1\cup I_2 & \ \text{otherwise}\end{array} \newline
\hspace{1cm} \cdot &T’&=&T_1\cup T_2\cup\lbrace (q,\sigma,q’)\mid(q,\sigma,f)\in T_1,f\in F_1,q’\in I_2\rbrace \newline
\end{array}$
| Notation | Explaination |
|---|---|
| $Q’$ | Same as Union, we include both automata for concatenation |
| $I’$ | We normaly start the the automaton from $I_1$ If $I_1$ is non-empty, otherwise we start at $I_2$ |
| $T’$ | For any states that can reach the accepting states of $T_1$ with one transition, we create a new transitions that reach the initial states of $T_2$ $(I_2)$ |
The correctness of this construction is proven by the following theorem.
$\textbf{Theorem 3.4. }\newline\textit{If $L_1$ is a regular language and $L_2$ is Büchi-recognizable, then $L_1\cdot L_2$ is Büchi-recognizable.}$
Explained in Human language
If $I_1$ is non-empty, then we can have a run that starts from $I_1$ to $r(n)$, that is one transition before $\mathcal{A_1}$’s accepting states of $f$. Then for next transition we either move to $f$, or we move on to $\mathcal{A_2}$ starting from $r(n+1)$.
If $I_1$ is empty, then any word accepted by $\mathcal{A‘}$ is accepted by $\mathcal{A_2}$
On the other way, we can always construct a word $w\alpha$. If $w$ is accepted by $\mathcal{A_1}$ and $\alpha$ is accepted by $\mathcal{A_2}$, then $w\alpha$ is always accepted by $\mathcal{A’}$
Formal Proof
We prove that the Büchi automaton $\mathcal{A’}$ built from the automaton on finite words $\mathcal{A}_1$ and the Büchi automaton $\mathcal{A}_2$ indeed recognizes the concatenation of the languages of the two automata.
$\mathcal{L}(\mathcal{A’})\subseteq\mathcal{L}(\mathcal{A}_1)\cdot\mathcal{L}(\mathcal{A}_2):$
For $\alpha\in\mathcal{L}(\mathcal{A’})$, we have an accepting run $r=r(0)r(1)r(2)\dots$ of $\mathcal{A’}$ on $\alpha$.
If $r(0)\in I_1$, then there is an $n\in\mathbb{N}$ such that $(r(n),\alpha(n),r(n+1))\in Q_1\times\Sigma\times I_2$ and therefore, there is a final state $f\in F_1$ such that $r(0)r(1)r(2)\dots r(n)f$ is an accepting run of $\mathcal{A_1}$ on $\alpha(0)\alpha(1)\alpha(2)\dots \alpha(n)$ and $r(n+1)r(n+2)\dots$ is an accepting run of $\mathcal{A_2}$ on $\alpha(n+1)\alpha(n+2)\dots$
If $r(0)\in I_2$ then $I_1\cup F_1 \neq\varnothing$ and therefore, $\varepsilon\in\mathcal{L}(\mathcal{A_1}),\alpha\in\mathcal{L}(\mathcal{A_2})$
$\mathcal{L}(\mathcal{A’})\supseteq\mathcal{L}(\mathcal{A}_1)\cdot\mathcal{L}(\mathcal{A}_2):$
For $w\in\mathcal{A_1}$, let $r=r(0)r(1)\dots r(n)$ be an accepting run $\mathcal{A_1}$ on $w$.
For $\alpha\in\mathcal{A_2}$, let $s=s(0)s(1)\dots$ be an accepting run of $\mathcal{A_2}$ on $\alpha$.
Then, $r(n)\in F_1$ and, by construction, $r(0)r(1)\dots r(n-1)s(0)s(1)\dots$ is an accepting run of $\mathcal{A’}$ on $w\alpha$.
Infinite concatenation of Regular language
Finally, we show that the infinite concatenation of words of a regular language forms a Büchi-recognizable language. We construct a Büchi automaton for this language from an automaton over finite words in two steps.
From automaton over finite words to a single initial state
Firstly, we modify a given automaton over finite words into an equivalent automaton with one single initial state that has no incoming transitions.
We do this by create a new fresh state as the new initial state, with all transitions identical as the original. And the original initial state now has no incoming transitions.
$\textbf{Construction 3.4. } \text{Let }\mathcal{A}_1=(\Sigma,Q_1,I_1,T_1,F_1)\text{ be an automaton over finite words. We assume}\newline\text{that }\varepsilon\notin\mathcal{L}(\mathcal{A})\text{. We construct an automaton }\mathcal{A’} = (\Sigma,Q’,I’,T’,F)\text{ over finite words such that }\newline\mathcal{L}(\mathcal{A})=\mathcal{L}(\mathcal{A’})\text{ and }\mathcal{A’}\text{ has a single initial state that has no incoming transitions.}$
$\begin{array}{lrll}
\hspace{1cm} \cdot &Q’&=&Q_1\cup\lbrace q_f\rbrace \text{where }q_f\text{ is a fresh state}\newline
\hspace{1cm} \cdot &I’&=&\lbrace q_f\rbrace\newline
\hspace{1cm} \cdot &T’&=&T\cup\lbrace (q_f,\sigma,q’)\mid(q,\sigma,q’)\in T \text{ for some }q\in I\rbrace\newline
\end{array}$
The second construction builds the Büchi automaton that recognizes the infinite concatenations of words from the regular language by adding a loop to the modified automaton.
$\textbf{Construction 3.5. } \text{Let }\mathcal{A}\text{ be an automaton over finite words. We assume that }\varepsilon\notin\mathcal{L}(\mathcal{A}).\newline\text{We construct a Büchi automaton }\mathcal{A’’}=(\Sigma,Q’’,I’’,T’’,\small\text{BÜCHI}\normalsize (F’’))\text{ such that }\mathcal{L}(\mathcal{A’’})=\mathcal{L}(\mathcal{A})^\omega.\newline\text{Let }\mathcal{A’}=(\Sigma,Q’,I’,T’,F’)\text{ be the automaton of Construction 3.4. Then }A’’\text{ is defined as follows:}$
$\begin{array}{l}
\hspace{1cm} \cdot \ Q’’=Q’ \hspace{1cm} \cdot \ I’’=I’ \hspace{1cm} \cdot \ F’’=I’\newline
\hspace{1cm} \cdot \ T’’=T’\cup\lbrace (q,\sigma,q_f)\mid(q,\sigma,q’)\in T’ \text{ and }q’\in F’\rbrace\newline
\end{array}$
This construction change the final state into the initial state, with adding new transition from final state to initial state. Therefore the automaton becomes a loop.
The correctness of this construction is proven by the following theorem.
$\textbf{Theorem 3.5. }\textit{If $L$ is a regular language such that $\varepsilon\notin L$, then $L^\omega$ is Büchi-recognizable}$
Explained in Human language
If there is accepting run for $\mathcal{L}(\mathcal{A’’})$, it reaches the accepting state infinitely often.
We can split the word in every accepting states and it will be an accepting run for $\mathcal{L}(\mathcal{A’})$, since the transition to accepting state $F’’$ and $F’$ are identical.
If there is accepting run(s) for $\mathcal{L}(\mathcal{A’})$, we can infinitely repeat them so that is also accepted for $\mathcal{L}(\mathcal{A’’})$.
Formal Proof
Construction 3.4 does not affect the language of $\mathcal{A}$. We show that the Büchi automaton $\mathcal{A’’}$ built in Construction 3.5 from the resulting automaton $\mathcal{A’}$ on finite words indeed recognizes $\mathcal{L}(\mathcal{A’})^\omega$.
$\mathcal{L}(\mathcal{A’’})\subseteq\mathcal{L}(\mathcal{A’})^\omega:$
Assume that $\alpha\in\mathcal{L}(\mathcal{A’’})$ and that $r(0)r(1)r(2)\dots$ is an accpeting run of $\mathcal{A’’}$ on $\alpha$. Hence, we have that $r(i)=q_f\in F’’=I’$ for inifinitely many indices $i:i_0,i_1,i_2,\dots$. This provides a sequence of runs of $\mathcal{A’}$:
- run $r(0)r(1)\dots r(i_0-1)q$ on $w_0= \alpha(0)\alpha(1)\dots\alpha(i_0-1)$ for some $q\in F’$
- run $r(i_0)r(i_0+1)\dots r(i_i-1)q$ on $w_1= \alpha(i_0)\alpha(i_1)\dots\alpha(i_1-1)$ for some $q\in F’$
- and so forth.
We thus have that $w_k\in\mathcal{L}(\mathcal{A’})$ for every $k\geq 0$. Hence, $\alpha\in\mathcal{L}(\mathcal{A’})^\omega$.
$\mathcal{L}(\mathcal{A’’})\supseteq\mathcal{L}(\mathcal{A’})^\omega:$
Assume that $\alpha =w_0w_1w_2\dots\in\Sigma^\omega$ such that $w_k\in\mathcal{L}(\mathcal{A’})$ for all $k\geq 0$. For each $k$, we choose an accepting run $r_k(0)r_k(1)r_k(2)\dots r_k(n_k)$ of $\mathcal{A’}$ on $w_k$. Hence, $r_k(0)\in I’$ and $r_k(n_k)\in F’$ for all $k>1$. Thus,
$$r_0(0)\dots r_0(n_0-1)r_1(0)\dots r_1(n_1-1)r_2(0)\dots r_2(n_2-1)\dots$$
is an accepting run of $\mathcal{A’’}$ on $\alpha$. Hence, $\alpha\in\mathcal{L}(\mathcal{A’’})$.
Summary
Now we proved the closure property holds for Union $(W_1\cup W_2)$, Intersection $(W_1\cap W_2)$, Concatenation of regular Langauge and Büchi-recognizable Language $(E+W)$, and Infinite concatenation of Regular language $(E^\omega)$.
In the next section we can start to prove Büchi’s Characterization Theorem.
Next chapter: Büchi’s Characterization Theorem
Further Reading: Closure (mathematics), Concatenation, Absolute infinite
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