AGV 3.4 -- Closure Properties of the Büchi-recognizable languages (Concatenations)

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