The star height of a regular expression $p$ over an alphabet $\Sigma$ , denoted by $\h(p)$ , is defined recursively as follows:

1. $\h(\varnothing)=\h(a)=0$ for any $a\in \Sigma$ ;
2. $\h(p\cup q)=\h(pq)=\max(\h(p),\h(q))$ ;
3. $\h(p^*)=\h(p)+1$ .

Let $\Sigma=\lbrace a,b,c\rbrace$ . The following expressions have star height $0,1,2,3$ : $$ (a\cup b)c \qquad a^*b^* \qquad (a^*b)^*c \qquad ((ab^*a \cup c)^* 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: $$\h(L)=\min \lbrace h(p) \mid L=L(p)\mbox{, }p\in R(\Sigma) \rbrace,$$ where $R(\Sigma)$ is the set of all regular expressions over $\Sigma$ .

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 $\Sigma$ 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 $|\Sigma|=2$ , then for every $n$ , there is a regular language $L$ over $\Sigma$ such that $\h(L)=n$ .
• It was an open question whether an algorithm exists for determining $\h(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 $\h_g(L)=\min \lbrace h(p) \mid L=L(p)\mbox{, }p\in R_g(\Sigma) \rbrace$ , where $R_g(\Sigma)$ is the set of all generalized regular expressions. It is clear that $\h_g(L)\le \h(L)$ . However, it is still an open question whether, for every integer $n$ , there is a regular language $L$ with $\h_g(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=\lbrace ab\rbrace^*$ .

Bibliography

1

A. Salomaa, Formal Languages, Academic Press, New York (1973).

2

A. Salomaa, Jewels of Formal Language Theory, Computer Science Press (1981).