Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?
$\begingroup$
$\endgroup$
-
$\begingroup$ (Random thought: is true that such a regular expression exists if and only if the minimal DFA of the language has no intersecting circles?) $\endgroup$ – Raphael♦ Mar 10 '15 at 7:42
-
$\begingroup$ @D.W. I looked on en.wikipedia.org/wiki/Star_height_problem to see if the known expressions of star-height 2 were close to this one, and if maybe I could reduce this to them. I also tried coming up with expressions of star-height 1, I looked at the syntactic monoid for inspiration, but for now I couldn't settle it... Raphael: No I think it is more complicated than that, computing star-height was an open problem for a long time. $\endgroup$ – Denis Mar 10 '15 at 8:47
$\begingroup$
$\endgroup$
The language has star-height 2. Note that the language includes $R_0=(ba^+ba^+)^*$, but is disjoint from $R_1=(ba^+ba^+)^*ba^+$. Therefore, it suffices to show:
Claim: If $L$ has star-height 1 and $R_0\subseteq L$, then $L\cap R_1\ne\emptyset$.
Suppose $L$ has star-height 1. Then we can write $L=\bigcup_{i=1}^m F_{i,0}^* w_{i,1} F_{i,1}^* \cdots w_{i,n} F_{i,n}^*$ for words $w_{i,j}$ and finite sets $F_{i,j}$.
We have $(ba^kba^k)^k\in R_0\subseteq L$ for every $k$. For $k$ large enough, there is some $F_{i,j}^*$ that contributes at least three $b$'s. Let us choose $k$ so large that also $k>|w|$ for any $w\in \bigcup_{i,j} F_{i,j}$.
Let $u$ be the factor with at least three $b$'s contributed by $F_{i,j}^*$. Then $u$ decomposes into factors $u_1,\ldots,u_m$ from $F_{i,j}$. Now we can clearly pick one or two consecutive $u_\ell$'s that together form a word $f\in a^+ba^+$. We can therefore repeat $f$ and obtain a word in $R_1$.
Update: Tried to be clearer.
