Star height
From Wikipedia, the free encyclopedia
In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression. The concept of star height was first defined and studied by Eggan (1963).
Contents |
[edit] Formal definition
More formally, the star height of a regular expression E over a finite alphabet A is inductively defined as follows:
, 
, and 
for all alphabet symbols a in A.
Here, 
is the special regular expression denoting the empty set and ε the special one denoting the empty word; E and F are arbitrary regular expressions.
The star height h(L) of a regular language L is defined as the minimum star height among all regular expressions representing L. The intuition is here that if the language L has large star height, then it is in some sense inherently complex, since it cannot be described by means of an "easy" regular expression, of low star height.
[edit] Examples
While computing the star height of a regular expression is easy, determining the star height of a language can be sometimes tricky. For illustration, the regular expression
over the alphabet A = {a,b} has star height 2. A trained reader might recognize that the described language is the set of all words ending in an a. Thus the language can be equivalently described by the expression
which is only of star height 1. To prove that this language indeed has star height 1, one still needs to rule out that it could be described by a regular expression of lower star height. For our example, this can be done by an indirect proof: One proves that a language of star height 0 contains only finitely many words. Since the language under consideration is infinite, it cannot be of star height 0.
[edit] 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 agree 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 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\"utzenberger (1965)).
[edit] See also
[edit] Notes
- Lawrence C. Eggan, Transition graphs and the star-height of regular events, Michigan Mathematical Journal, 10(4): 385–397, 1963.
- Schützenberger M.P. (1965). "On Finite monoids having only trivial subgroups". Information and Computation 8 (2): 190–194.
