Star height
From Free net encyclopedia
(Difference between revisions)
Revision as of 18:32, 19 April 2006
Pascal.Tesson (Talk | contribs)
sorry, got the editing wrong
Next diff →
Pascal.Tesson (Talk | contribs)
sorry, got the editing wrong
Next diff →
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(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).
See also star heightproblem and generalized star height problem.
[edit]
Notes
<references/>it:Altezza star