Star Height

The star height of a regular language is the minimum, over its ordinary regular expressions, of the maximum nesting depth of Kleene stars. Ordinary expressions use union, concatenation, and Kleene star, without complement. An expression with no star has height zero; a star increases the height of its argument by one.

Generalized star height permits complement as well, so it can be smaller than ordinary star height. A bound for generalized star height does not by itself bound ordinary star height.