<p>Sure. In fact, the translation from Büchi automata to <span class="math-container">$\omega$</span>-regular expressions is only a small extension of the one for finite-word languages.</p>

<p>Recall that an <span class="math-container">$\omega$</span>-regular expression is of the form <span class="math-container">$s_1\cdot t_1^\omega+\ldots+s_k \cdot t_k^\omega$</span>, where all the <span class="math-container">$s_i$</span> and <span class="math-container">$t_i$</span> are regular expressions.</p>

<p>The translation of an NBW <span class="math-container">$A$</span> to such an expression is based on the following observation: let <span class="math-container">$A_{p,q}$</span> be the NFA obtained from <span class="math-container">$A$</span> by setting <span class="math-container">$p$</span> as the initial state, and <span class="math-container">$q$</span> as the single accepting state, then <span class="math-container">$L(A)=\bigcup_{q\in \alpha} L(A_{q_0,q})\cdot L(A_{q,q})^\omega$</span> where <span class="math-container">$\alpha$</span> is the set of accepting states of <span class="math-container">$A$</span>.</p>

<p>Indeed, a word is accepted by <span class="math-container">$A$</span> iff there is a run on it that leads from <span class="math-container">$q_0$</span> to an accepting state <span class="math-container">$q$</span>, that is then visited infinitely often.</p>

<p>So all you need to do is write the equations that correspond to this union. It'll be slightly uglier than those for an NFA, but not much.</p>

CC BY-SA 4.0
2020-04-26T15:45:24.443Z
Thank you, that is the answer I need.
yrZhang
CC BY-SA 4.0
2020-04-21T18:01:56.550Z
2020-04-21T19:45:55.603Z
2020-04-21T19:45:55.603Z
Shaull
<p>I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows.
      First we construct a set of equations named "(1)" based on an automaton <span class="math-container">$A$</span>:
            <span class="math-container">\begin{equation}\begin{aligned}&amp;l_1 = \varepsilon + p_{11}l_1 + p_{12}l_2 + ... + p_{1n}l_n\\
                         &amp;l_2 = \varepsilon + p_{21}l_1 + p_{22}l_2 + ... + p_{2n}l_n\\
                         &amp;...\\
                         &amp;l_n = \varepsilon + p_{n1}l_1 + p_{n2}l_2 + ... + p_{nn}l_n, \end{aligned}\end{equation}</span>
where are <span class="math-container">$l_1,...,l_n$</span> are the locations (or called "states") of <span class="math-container">$A$</span> with <span class="math-container">$l_1$</span> the initial location, <span class="math-container">$p_{ij}$</span> are regular expressions. Then we apply Arden's rule: </p>

<p>"<span class="math-container">$X = p^*q$</span> is the unique solution for equation <span class="math-container">$X = q + pX$</span>"</p>

<p>to solve the equations. The result of <span class="math-container">$l_1$</span> is the regular expression we want. </p>

<p>Now my question is, <strong>is there a similar method for transforming Büchi automata into omega-regular language</strong>? </p>

<automata-theory><omega-language>
Is there any equation-based method for transforming Büchi-automata to omega-regular language?
yrZhang
# Is there any equation-based method for transforming Büchi-automata to omega-regular language?

(Asked by: username_0 on 2020-04-21)

I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows.
First we construct a set of equations named "(1)" based on an automaton $A$:
\begin{equation}\begin{aligned}&l\_1 = \varepsilon + p\_{11}l\_1 + p\_{12}l\_2 + ... + p\_{1n}l\_n\\
&l\_2 = \varepsilon + p\_{21}l\_1 + p\_{22}l\_2 + ... + p\_{2n}l\_n\\
&...\\
&l\_n = \varepsilon + p\_{n1}l\_1 + p\_{n2}l\_2 + ... + p\_{nn}l\_n, \end{aligned}\end{equation}
where are $l\_1,...,l\_n$ are the locations (or called "states") of $A$ with $l\_1$ the initial location, $p\_{ij}$ are regular expressions. Then we apply Arden's rule:

"$X = p^\*q$ is the unique solution for equation $X = q + pX$"

to solve the equations. The result of $l\_1$ is the regular expression we want.

Now my question is, **is there a similar method for transforming Büchi automata into omega-regular language**?

**Tags:** automata-theory, omega-language

---

## 1 answers

### Answer by username_1 on 2020-04-21. Score: 6 | Accepted answer

Sure. In fact, the translation from Büchi automata to $\omega$-regular expressions is only a small extension of the one for finite-word languages.

Recall that an $\omega$-regular expression is of the form $s\_1\cdot t\_1^\omega+\ldots+s\_k \cdot t\_k^\omega$, where all the $s\_i$ and $t\_i$ are regular expressions.

The translation of an NBW $A$ to such an expression is based on the following observation: let $A\_{p,q}$ be the NFA obtained from $A$ by setting $p$ as the initial state, and $q$ as the single accepting state, then $L(A)=\bigcup\_{q\in \alpha} L(A\_{q\_0,q})\cdot L(A\_{q,q})^\omega$ where $\alpha$ is the set of accepting states of $A$.

Indeed, a word is accepted by $A$ iff there is a run on it that leads from $q\_0$ to an accepting state $q$, that is then visited infinitely often.

So all you need to do is write the equations that correspond to this union. It'll be slightly uglier than those for an NFA, but not much.

> **Comments:**
> **username_0**: Thank you, that is the answer I need.  

---

