2
$\begingroup$

Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?

$\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
3
$\begingroup$

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.

$\endgroup$

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.