# Star height problem (Solved)

**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.

## This was solved ages ago!

See the referenced Wikipedia article.