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)
“And tell so readily, he knoweth well
How ev’ry star by proper name to call?”
—Bible: Hebrew Psalm CXLVII (Paraphrased by The Countess of Pembroke)
“The enemy are no match for us in a fair fight.... The young men ... of the upper class are kind-hearted, good-natured fellows, who are unfit as possible for the business they are in. They have courage but no endurance, enterprise, or energy. The lower class are cowardly, cunning, and lazy. The height of their ambition is to shoot a Yankee from some place of safety.”
—Rutherford Birchard Hayes (1822–1893)