The
star-height problem in [formal language theory]
? is the question whether all
regular languages be expressed using
regular expressions with a limited nesting depth of
Kleene stars?
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 [Kosaburo Hashiguchi]
? in 1983. The answer is yes.
The generalized star height problem is the same problem for regular expressions that include the complement operator. This is still an open problem.