Star height

From Wikipedia, the free encyclopedia

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

• h(∅) = 0, h(ε) = 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).

See also star height problem and generalized star height problem.

[edit] Notes

1. ^ The definition given here is that of generalized star height since regular expressions are allowed to use the complement operator.