The maximum depth to which the Kleene star operator is nested in a given regular expression. The star-height of a regular language L is the smallest star-height of any regular expression for L. There is no known algorithm for determining the star-height of a regular language. It is however known that there are regular languages of arbitrary star-height.

If complement and intersection are allowed, the class of generalized regular expressions is obtained. For these it is not known if there are languages of star-height greater than one.