# Why is $((aa)^*bb(aa)^*bb(aa)^*)^*$ of star-height 1

A generalized regular expression is like a regular expression but with one more operation allowed: complementation. The (generalized) star-height of a generalized regular expression is the maximal number of nested Kleene stars. The star-height of a language is the minimal star-height of a regular expression describing it. It is not known if there is even a language of star-height 2.

So I imagine the langage $$((aa)^*bb(aa)^*bb(aa)^*)^*(aa)^*$$ of words consisting of concatenations of $$aa$$ and $$bb$$, with an even number of $$bb$$, is of generalized star-height $$1$$. But I couldn't prove it. In the paper Some results on the generalized star-height problem (Pin, Straubing, Thérien), lemma 6.1 (the transfer lemma) cannot be applied because both $$(bb)^*$$ and $$(aa)^*$$ are of star-height 1.

I saw elsewhere some languages which were conjectured to be of star-height 2 and they were more complex than the one I give, so it is very probably of star-height 1. Is it the case?

• Did you look at the complement? Either strings not of the form "(aa+bb)*", or strings with an odd number of bb with in between "a (not bb) a". The "not bb" are the complement of (a+b)*bb(a+b)*. As you know (a+b)* is starheight zero. Aug 27 '20 at 15:17
• @HendrikJan Hi and thank you but I couldn't understand what you said. So yes first we can restrict our attention to strings of the form $(aa+bb)^*$ (we don't care about the other ones). Strings that do not contain $bb$ are also of star-height 1, ok. But what do you mean by strings with an odd number of bb with in between "a (not bb) a"''? The problem is I don't know how to count parity. Aug 28 '20 at 0:18
• @HendrikJan I don't see how it helps to shift attention to the complement, because when restricting the attention to strings of the form $(aa+bb)^*$, we will need to count strings with an odd number of $bb$, which seems to be of the same difficulty. Aug 28 '20 at 0:19

(This is an attempt to an answer, I hope the details are right.)

Your language consists of all strings in $$(aa+bb)^*$$ with an even number of $$bb$$.

We are allowed to use complementation, so we start by looking at the complement of the language. I think we can split the complement into two (overlapping) parts

• strings not of the form $$(aa+bb)^*$$, that language has starheight one.
• strings of the form $$w_0\cdot bb\cdot w_1\cdot bb\cdot w_2 \dots bb\cdot w_n$$, where (1) the number of $$bb$$ is odd, and (2) the $$w_i$$ do not contain any $$bb$$ (but I will have to be more precise on that)

Now we will try to find an expression for the language $$W$$ of the $$w_i$$ without using star. That means we can use the star to count the odd number of $$bb$$, as in $$(W\cdot bb\cdot W\cdot bb)^*\cdot W\cdot bb\cdot W$$.

This is the tricky part. Strings from $$W$$ are either

• the empty string $$\varepsilon$$
• just one single $$a$$
• of the form $$axa$$, where $$a$$ does not contain $$bb$$. Not "containing $$bb$$" is the complement of $$(a+b)^*bb(a+b)^*$$, and as you know $$(a+b)^*$$ is again star-free.

The strings we now have specified can have longer stretches of $$b$$'s, but whenever that happens the $$b$$'s come in pairs.

• Aaah yes, thank you very much. Your idea is right but actually it is useless to take the complementary. The language I gave is explicitely $(aa+bb)^* ∩ (a^*bba^*bba^*)^*a^*$. They are simply the words of $(aa+bb)^*$ that contain a number of $b$s divisible by 4. I'm stupid... Aug 28 '20 at 10:54
• @Idéophage Sorry, but now you have to help me: why does it help? How do you get rid of the intersection? Aug 28 '20 at 23:13
• Well, since we can use complementation, we can actually use all boolean operations : $X ∩ Y = \overline{\overline{X} ∪ \overline{Y}}$. :) Maybe you were thinking too much about restricted star-height. Aug 28 '20 at 23:37
• Thanks, I simply did not realize this... We all have our stupid days it seems ... Aug 29 '20 at 1:41