for any ;
Let . The following expressions have star height :
Since any regular expression describes a regular language , we may extend the definition of star height to regular languages. However, since a regular language may be described by more than one regular expressions, we need to be a little careful:
The star height of a regular language is the least integer such that may be described by a regular expression of star height . In other words:
where is the set of all regular expressions over .
Any regular language over a singleton alphabet has star height at most 1, which can be proved by the pumping lemma for regular languages.
If the alphabet consists of at least two letters, then for every positive integer , there is a regular language whose star height is . In fact, it can be shown that if , then for every , there is a regular language over such that .
We may also define star height on generalized regular expressions. For a regular language , define , where is the set of all generalized regular expressions. It is clear that . However, it is still an open question whether, for every integer , there is a regular language with .
A star-free language has star height with respect to representations by generalized regular expressions, but may be positive with respect to representations by regular expressions, for example .
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
- 2 A. Salomaa, Jewels of Formal Language Theory, Computer Science Press (1981).
|Date of creation||2013-03-22 18:57:55|
|Last modified on||2013-03-22 18:57:55|
|Last modified by||CWoo (3771)|