The generalized star height of a regular language is the least possible maximum nesting depth of Kleene stars in a generalized regular expression defining it. A generalized expression uses union, concatenation, Kleene star, and complement relative to all finite words over the fixed alphabet. Complement is permitted in this definition, whereas ordinary regular expressions omit it.
Generalized Star Height
See also
Kleene Star, Regular Expression, Regular Language, Star HeightExplore with Wolfram|Alpha
References
Pin, J.-É.; Straubing, H.; and Thérien, D. "Some Results on the Generalized Star-Height Problem." Inform. Comput. 101, 219-250, 1992. https://doi.org/10.1016/0890-5401(92)90063-L.Cite this as:
Weisstein, Eric W. "Generalized Star Height." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GeneralizedStarHeight.html