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?

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 27 '20 at 15:17
  • $\begingroup$ @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. $\endgroup$
    – Idéophage
    Aug 28 '20 at 0:18
  • $\begingroup$ @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. $\endgroup$
    – Idéophage
    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.

  • $\begingroup$ 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... $\endgroup$
    – Idéophage
    Aug 28 '20 at 10:54
  • $\begingroup$ @Idéophage Sorry, but now you have to help me: why does it help? How do you get rid of the intersection? $\endgroup$ Aug 28 '20 at 23:13
  • $\begingroup$ 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. $\endgroup$
    – Idéophage
    Aug 28 '20 at 23:37
  • $\begingroup$ Thanks, I simply did not realize this... We all have our stupid days it seems ... $\endgroup$ Aug 29 '20 at 1:41

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.