Star height

From Free net encyclopedia

---

Current revision

In mathematics, the star height h(E) of a regular expression E over a finite alphabet A is defined as follows<ref> The definition given here is that of generalized star height since regular expressions are allowed to use the complement operator.</ref>:

• 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 heightproblem and generalized star height problem.

Notes

<references/>it:Altezza star