Conjecture The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required?
Bibliography
*Lawrence C. Eggan: Transition graphs and the star-height of regular events, Michigan Mathematical Journal, 10(4): 385–397, 1963.
* indicates original appearance(s) of problem.