Generalized Star Height
The above definition assumes that regular expressions are built from the elements of the alphabet A using only the standard operators set union, concatenation, and Kleene star. Generalized regular expressions are defined just as regular expressions, but here also the set complement operator is allowed (the complement is always taken with respect to the set of all words over A). If we alter the definition such that taking complements does not increase the star height, that is,
we can define the generalized star height of a regular language L as the minimum star height among all generalized regular expressions representing L.
Note that, whereas it is immediate that a language of (ordinary) star height 0 can contain only finitely many words, there exist infinite languages having generalized star height 0. For instance, the regular expression
which we saw in the example above, can be equivalently described by the generalized regular expression
- ,
since the complement of the empty set is precisely the set of all words over A. Thus the set of all words over the alphabet A ending in the letter a has star height one, while its generalized star height equals zero.
Languages of generalized star height zero are also called star-free languages. It can be shown that a language L is star-free if and only if its syntactic monoid is aperiodic (Schützenberger (1965)).
Read more about this topic: Star Height
Famous quotes containing the words generalized, star and/or height:
“One is conscious of no brave and noble earnestness in it, of no generalized passion for intellectual and spiritual adventure, of no organized determination to think things out. What is there is a highly self-conscious and insipid correctness, a bloodless respectability submergence of matter in manner—in brief, what is there is the feeble, uninspiring quality of German painting and English music.”
—H.L. (Henry Lewis)
“One thing about being successful is that I stopped being afraid of dying. Once you’re a star you’re dead already. You’re embalmed.”
—Dustin Hoffman (b. 1937)
“Tell me of the height of the mountains of the moon, or of the diameter of space, and I may believe you, but of the secret history of the Almighty, and I shall pronounce thee mad.”
—Henry David Thoreau (1817–1862)