The story
From the Kleene star and the idea of nested levels having a "height"; coined in 1963 by Lawrence C Eggan.
Etymology from Wiktionary, CC BY-SA 4.0.
star height
Today it means: A measure of the structural complexity of a regular expression, equal to the maximum nesting depth of stars in the expression. Full definition →