star height


The star height of a regular expressionMathworldPlanetmath p over an alphabet Σ, denoted by ht(p), is defined recursively as follows:

  1. 1.

    ht()=ht(a)=0 for any aΣ;

  2. 2.

    ht(pq)=ht(pq)=max(ht(p),ht(q));

  3. 3.

    ht(p*)=ht(p)+1.

Let Σ={a,b,c}. The following expressions have star height 0,1,2,3:

(ab)c  a*b*  (a*b)*c  ((ab*ac)*b)*

Since any regular expression p describes a regular language L(p), 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 L is the least integer i such that L may be described by a regular expression of star height i. In other words:

ht(L)=min{h(p)L=L(p)pR(Σ)},

where R(Σ) is the set of all regular expressions over Σ.

Remarks.

  • 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 n, there is a regular language whose star height is n. In fact, it can be shown that if |Σ|=2, then for every n, there is a regular language L over Σ such that ht(L)=n.

  • It was an open question whether an algorithmMathworldPlanetmath exists for determining ht(L) for an arbitrary regular language L. In 2005, the question was resolved by D. Kirsten in the positive, and the algorithm is that of a non-deterministic finite automaton.

  • We may also define star height on generalized regular expressions. For a regular language L, define htg(L)=min{h(p)L=L(p)pRg(Σ)}, where Rg(Σ) is the set of all generalized regular expressions. It is clear that htg(L)ht(L). However, it is still an open question whether, for every integer n, there is a regular language L with htg(L)=n.

    A star-free language has star height 0 with respect to representations by generalized regular expressions, but may be positive with respect to representations by regular expressions, for example L={ab}*.

References

  • 1 A. Salomaa, Formal LanguagesMathworldPlanetmath, Academic Press, New York (1973).
  • 2 A. Salomaa, Jewels of Formal Language Theory, Computer Science Press (1981).
Title star height
Canonical name StarHeight
Date of creation 2013-03-22 18:57:55
Last modified on 2013-03-22 18:57:55
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 20M35
Classification msc 68Q70
Related topic StarFree