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(Ec) = 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).