If we only use regular expression
s with a limited nesting depth of Kleene star
s, 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
the star height problem is still open; for details see
!(a u ab)*