<p>The examples of arbitrary star-height given on the <a href="https://en.wikipedia.org/wiki/Star_height_problem" rel="noreferrer">wikipedia page on the star-height problem</a> are star-free:</p>
<p>On arbitrary alphabet:
:<span class="math-container">\begin{alignat}{2}
e_1 &amp;= a_1^* \\
e_2 &amp;= \left(a_1^*a_2^*a_3\right)^*\\
e_3 &amp;= \left(\left(a_1^*a_2^*a_3\right)^*\left(a_4^*a_5^*a_6\right)^*a_7\right)^*\\
e_4 &amp;= \left(
\left(\left(a_1^*a_2^*a_3\right)^*\left(a_4^*a_5^*a_6\right)^*a_7\right)^*
\left(\left(a_8^*a_9^*a_{10}\right)^*\left(a_{11}^*a_{12}^*a_{13}\right)^*a_{14}\right)^*
a_{15}\right)^*\\
&amp;\dots\\
e_{n+1}&amp;= (e_ne'_n a_{2^{n+1}-1})^*
\end{alignat}</span>

where <span class="math-container">$e'_n$</span> is a copy of <span class="math-container">$e_n$</span> with fresh letters <span class="math-container">$a_{2^n},\dots ,a_{2^{n+1}-2}$</span>, and <span class="math-container">$a_{2^{n+1}-1}$</span> is another fresh letter.</p>
<p>On binary alphabet:
<span class="math-container">\begin{alignat}{2}
e_1 &amp; = (ab)^* \\
e_2 &amp; = \left(aa(ab)^*bb(ab)^*\right)^* \\
e_3 &amp; = \left(aaaa \left(aa(ab)^*bb(ab)^*\right)^* bbbb \left(aa(ab)^*bb(ab)^*\right)^*\right)^* \\
\, &amp; \cdots \\
e_{n+1} &amp; = (\,\underbrace{a\cdots a}_{2^n}\, \cdot \, e_n\, \cdot\, \underbrace{b\cdots b}_{2^n}\, \cdot\, e_n \,)^*
\end{alignat}</span>
</p>
<p>Intuitively, we can see these languages never need to count modulo, so they are star-free.
To prove formally that <span class="math-container">$e_n$</span> always describes a star-free language, you can for example show by induction that the NFAs obtained from these expressions have no &quot;counter&quot;, i.e. no path of the form <span class="math-container">$p\stackrel{u}{\to}q\stackrel{u^k}{\to}p$</span> with <span class="math-container">$p\neq q$</span>.</p>

CC BY-SA 4.0
2021-10-19T10:30:10.213Z
Thanks @Denis ! I feel silly, I did not realized that these are star-free (to be honest that's still not obvious, though the "no counter" characterization is nice, I don't see an obvious star-free regular expression equivalent to $e_2$).
thibo
CC BY-SA 4.0
2021-10-19T11:11:04.833Z
For instance for $e_2$ it's simply the words that do not contain the factor $a_2a_1$. So your star-free expression is $\overline{\overline{\emptyset}a_2a_1\overline{\emptyset}}$.
Denis
CC BY-SA 4.0
2021-10-19T11:20:41.420Z
Also you have to end with $a_3$ if the word is not empty, but you can incorporate that as well. Actually I believe all expressions $e_n$ of the arbitrary alphabet case amount to forbid a bunch of two-letter factors, together with conditions on the first and last letters.
Denis
CC BY-SA 4.0
2021-10-19T11:58:18.230Z
Thanks a lot! I meant  $e_2=(aa(ab)^*bb(ab)^*)$. I guess something along $\Sigma^* \setminus (b\Sigma^* \cup \Sigma^*a \cup ab\Sigma^* \cup \Sigma^*(a^4+b^4)\Sigma^* \cup \Sigma^*a^3(ba)^*b^3 \cup \Sigma^*b^3(ba)^*a^3)$, but I might be missing some cases.
thibo
CC BY-SA 4.0
2021-10-19T13:34:11.317Z
We have intersection so it might be easier to list constraints. Maybe first-order logic or LTL are more convenient to express these languages. Since these formalisms capture star-free languages you can also use them here. For instance for $e_2$, you can say that any occurrence of $aa$ (which is not after another $a$) is followed by a factor of the form $(ab)^*(bb)$, using a first-order or LTL formula. This is maybe the simplest way to prove by induction that they are all FO-definable.
Denis
CC BY-SA 4.0
2021-10-27T09:51:30.690Z
Thanks again! Do you know if there exists any algorithm which transforms a (restricted) regular expression of a star-free language into an equivalent generalized star height $1$ (generalized) regular expression? The converse is OK since you can apply the usual Thompson's construction + determinization + complement of DFA (there might be a more efficient way though), but I don't see an obvious way for the other direction
thibo
CC BY-SA 4.0
2021-10-27T10:16:56.433Z
Do you mean generalized star-height 0 (i.e. star-free) ? Yes there is such an algorithm: you can compute an aperiodic monoid for your language, and then the proof that aperiodic monoids are equivalent to star-free expressions is constructive: it can be turned into an algorithm to compute such an expression from the monoid.
Denis
CC BY-SA 4.0
2021-10-27T10:18:37.560Z
See for instance http://www.lsv.fr/Publis/PAPERS/PDF/DG-WT08.pdf for all relevant definitions and constructions.
Denis
CC BY-SA 4.0
2021-10-18T21:58:16.437Z
2021-10-19T11:12:51.120Z
2021-10-19T11:12:51.120Z
Denis
<p>I'm interested in the (restricted) star-height of star free-languages.</p>
<p>Recalling the definitions:
the <em>star height</em> <span class="math-container">$h(\mathtt{e})$</span> of a regular expression <span class="math-container">$\mathtt{e}$</span> is</p>
<ul>
<li><span class="math-container">$0$</span> if <span class="math-container">$\mathtt{e}= \varepsilon$</span> or <span class="math-container">$a \in \Sigma$</span></li>
<li><span class="math-container">$\max(h(\mathtt{f}),h(\mathtt{f'}))$</span> if <span class="math-container">$\mathtt{e}=\mathtt{f+f'}$</span> or <span class="math-container">$\mathtt{f.f'}$</span></li>
<li><span class="math-container">$1+h(\mathtt{f})$</span> if <span class="math-container">$\mathtt{e}=\mathtt{f ^*}$</span></li>
</ul>
<p>The star height of a languages is the smallest star height among the regular expressions describing the language.</p>
<p>On the other hand, the <em>star free</em> languages is the smallest set of languages containing the empty set and each individual letter, and closed under concatenation, union and complement (thus also intersection).</p>
<hr />
<p>I know that the languages of star height <span class="math-container">$0$</span> are the finite languages, and that star-free languages can have positive star height.
I also know that a family of witnesses for the infinity of the star height hierarchy is the set of languages <span class="math-container">$L_n= \{\mathbf{w} \in \Sigma^* \quad |\quad |\mathbf{w}|_a= |\mathbf{w}|_b\equiv 0 \mod (2^n)  \}$</span>, but these are not star-free</p>
<p>My question is <em>can a star-free language have an arbitrary large star height</em>?</p>
<p>disclaimer: I might be missing some obvious point, but a quick internet check was not productive</p>

<fl.formal-languages><regular-language><regular-expressions><monoid>
star height of star-free languages
thibo
# star height of star-free languages

(Asked by: username_0 on 2021-10-18)

I'm interested in the (restricted) star-height of star free-languages.

Recalling the definitions:
the *star height* $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is

* $0$ if $\mathtt{e}= \varepsilon$ or $a \in \Sigma$
* $\max(h(\mathtt{f}),h(\mathtt{f'}))$ if $\mathtt{e}=\mathtt{f+f'}$ or $\mathtt{f.f'}$
* $1+h(\mathtt{f})$ if $\mathtt{e}=\mathtt{f ^\*}$

The star height of a languages is the smallest star height among the regular expressions describing the language.

On the other hand, the *star free* languages is the smallest set of languages containing the empty set and each individual letter, and closed under concatenation, union and complement (thus also intersection).

---

I know that the languages of star height $0$ are the finite languages, and that star-free languages can have positive star height.
I also know that a family of witnesses for the infinity of the star height hierarchy is the set of languages $L\_n= \{\mathbf{w} \in \Sigma^\* \quad |\quad |\mathbf{w}|\_a= |\mathbf{w}|\_b\equiv 0 \mod (2^n) \}$, but these are not star-free

My question is *can a star-free language have an arbitrary large star height*?

disclaimer: I might be missing some obvious point, but a quick internet check was not productive

**Tags:** fl.formal-languages, regular-language, regular-expressions, monoid


---

## 1 answers

### Answer by username_1 on 2021-10-18. Score: 7 | Accepted answer

The examples of arbitrary star-height given on the [wikipedia page on the star-height problem](https://en.wikipedia.org/wiki/Star_height_problem) are star-free:

On arbitrary alphabet:
:\begin{alignat}{2}
e\_1 &= a\_1^\* \\
e\_2 &= \left(a\_1^\*a\_2^\*a\_3\right)^\*\\
e\_3 &= \left(\left(a\_1^\*a\_2^\*a\_3\right)^\*\left(a\_4^\*a\_5^\*a\_6\right)^\*a\_7\right)^\*\\
e\_4 &= \left(
\left(\left(a\_1^\*a\_2^\*a\_3\right)^\*\left(a\_4^\*a\_5^\*a\_6\right)^\*a\_7\right)^\*
\left(\left(a\_8^\*a\_9^\*a\_{10}\right)^\*\left(a\_{11}^\*a\_{12}^\*a\_{13}\right)^\*a\_{14}\right)^\*
a\_{15}\right)^\*\\
&\dots\\
e\_{n+1}&= (e\_ne'\_n a\_{2^{n+1}-1})^\*
\end{alignat}
where $e'\_n$ is a copy of $e\_n$ with fresh letters $a\_{2^n},\dots ,a\_{2^{n+1}-2}$, and $a\_{2^{n+1}-1}$ is another fresh letter.

On binary alphabet:
\begin{alignat}{2}
e\_1 & = (ab)^\* \\
e\_2 & = \left(aa(ab)^\*bb(ab)^\*\right)^\* \\
e\_3 & = \left(aaaa \left(aa(ab)^\*bb(ab)^\*\right)^\* bbbb \left(aa(ab)^\*bb(ab)^\*\right)^\*\right)^\* \\
\, & \cdots \\
e\_{n+1} & = (\,\underbrace{a\cdots a}\_{2^n}\, \cdot \, e\_n\, \cdot\, \underbrace{b\cdots b}\_{2^n}\, \cdot\, e\_n \,)^\*
\end{alignat}

Intuitively, we can see these languages never need to count modulo, so they are star-free.
To prove formally that $e\_n$ always describes a star-free language, you can for example show by induction that the NFAs obtained from these expressions have no "counter", i.e. no path of the form $p\stackrel{u}{\to}q\stackrel{u^k}{\to}p$ with $p\neq q$.

> **Comments:**
> **username_0**: Thanks @username_1 ! I feel silly, I did not realized that these are star-free (to be honest that's still not obvious, though the "no counter" characterization is nice, I don't see an obvious star-free regular expression equivalent to $e_2$).  
> **username_1**: For instance for $e_2$ it's simply the words that do not contain the factor $a_2a_1$. So your star-free expression is $\overline{\overline{\emptyset}a_2a_1\overline{\emptyset}}$.  
> **username_1**: Also you have to end with $a_3$ if the word is not empty, but you can incorporate that as well. Actually I believe all expressions $e_n$ of the arbitrary alphabet case amount to forbid a bunch of two-letter factors, together with conditions on the first and last letters.  
> **username_0**: Thanks a lot! I meant  $e_2=(aa(ab)^*bb(ab)^*)$. I guess something along $\Sigma^* \setminus (b\Sigma^* \cup \Sigma^*a \cup ab\Sigma^* \cup \Sigma^*(a^4+b^4)\Sigma^* \cup \Sigma^*a^3(ba)^*b^3 \cup \Sigma^*b^3(ba)^*a^3)$, but I might be missing some cases.  
> **username_1**: We have intersection so it might be easier to list constraints. Maybe first-order logic or LTL are more convenient to express these languages. Since these formalisms capture star-free languages you can also use them here. For instance for $e_2$, you can say that any occurrence of $aa$ (which is not after another $a$) is followed by a factor of the form $(ab)^*(bb)$, using a first-order or LTL formula. This is maybe the simplest way to prove by induction that they are all FO-definable.  
> **username_0**: Thanks again! Do you know if there exists any algorithm which transforms a (restricted) regular expression of a star-free language into an equivalent generalized star height $1$ (generalized) regular expression? The converse is OK since you can apply the usual Thompson's construction + determinization + complement of DFA (there might be a more efficient way though), but I don't see an obvious way for the other direction  
> **username_1**: Do you mean generalized star-height 0 (i.e. star-free) ? Yes there is such an algorithm: you can compute an aperiodic monoid for your language, and then the proof that aperiodic monoids are equivalent to star-free expressions is constructive: it can be turned into an algorithm to compute such an expression from the monoid.  
> **username_1**: See for instance http://www.lsv.fr/Publis/PAPERS/PDF/DG-WT08.pdf for all relevant definitions and constructions.  

---

