If we only use
regular expressions with a limited nesting depth of
Kleene stars, are there
regular languages we cannot express?
Specifically, is a nesting depth of more than 2 required?
If so, can we determine how many are required?
This theoretical problem remained open for 30 years, to be solved by Kosaburu Hashiguchi in 1983. The answers are yes, yes, and yes.
However, for regular expression with complementation, in which we can
write things like
!(a u ab)*
the star height problem is still open; for details see
http://www.liafa.jussieu.fr/~jep/Problemes/starheight.html