6
$\begingroup$

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

Improve this question
$\endgroup$
7
$\begingroup$

The examples of arbitrary star-height given on the wikipedia page on the 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$.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ 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$). $\endgroup$
    – thibo
    Oct 19 at 10:30
  • 1
    $\begingroup$ 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}}$. $\endgroup$
    – Denis
    Oct 19 at 11:11
  • $\begingroup$ 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. $\endgroup$
    – Denis
    Oct 19 at 11:20
  • $\begingroup$ 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. $\endgroup$
    – thibo
    Oct 19 at 11:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Denis
    Oct 27 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.