Star height

In mathematics, the star height h(E) of a regular expression E over a finite alphabet A is defined as follows:

• h(∅) = 0, h(1) = 0, h(a) = 0 for all a ∈ A.
• h(E ∩ F) = h(EF) = max(h(E), h(F))
• h(E^c) = h(E)
• h(E^*) = h(E) + 1

The star height h(L) of a regular language L is defined as the minimum of the star heights of all regular expressions representing L.

It can be shown that a language L has star height 0 iff its syntactic monoid is aperiodic (Schützenberger 1965).