| 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)*
http://www.liafa.jussieu.fr/~jep/Problemes/starheight.html
| 
