Encyclopedia

Star height problem

Problem in formal language theory

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated August 27, 2026

In formal language theory, the star height problem is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required? The problem was first introduced by Eggan in 1963.

01Families of regular languages with unbounded star height

The first question was answered in the negative when in 1963, Eggan gave examples of regular languages of star height $n$ for every $n$ . Here, the star height of a regular language $L$ is defined as the minimum star height among all regular expressions representing $L$ . The first few languages found by Eggan are described in the following, by means of giving a regular expression for each language:

${\begin{alignedat}{2}e_{1}&=a_{1}^{*}\\e_{2}&=\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\\e_{4}&=\left(\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\left(\left(a_{8}^{*}a_{9}^{*}a_{10}\right)^{*}\left(a_{11}^{*}a_{12}^{*}a_{13}\right)^{*}a_{14}\right)^{*}a_{15}\right)^{*}\end{alignedat}}$

The construction principle for these expressions is that expression $e_{n+1}$ is obtained by concatenating two copies of $e_{n}$ , appropriately renaming the letters of the second copy using fresh alphabet symbols, concatenating the result with another fresh alphabet symbol, and then by surrounding the resulting expression with a Kleene star. Eggan proved that, for each $e_{n}$ , there is no equivalent regular expression of star height less than $n$ .

However, Eggan's examples use a large alphabet, of size $2^{n}-1$ for the language with star height $n$ . He thus asked whether we can also find examples over binary alphabets. This was proved to be true shortly afterwards by Dejean and Schützenberger in 1966. Their examples can be described by an inductively defined family of regular expressions over the binary alphabet $\{a,b\}$ as follows:

${\begin{alignedat}{2}e_{1}&=(ab)^{*}\\e_{2}&=\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\\e_{3}&=\left(aaaa\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}bbbb\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\right)^{*}\\\,&\cdots \\e_{n+1}&=(\,\underbrace {a\cdots a} _{2^{n}}\,\cdot \,e_{n}\,\cdot \,\underbrace {b\cdots b} _{2^{n}}\,\cdot \,e_{n}\,)^{*}\end{alignedat}}$

02Computing the star height of regular languages

Eggan's second question, i.e., whether there exists an algorithm to determine the star height of a language, turned out to be much more difficult. The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be decidable. The general problem remained open until it was settled by Hashiguchi in 1988, who published an algorithm to determine the star height of any regular language. The algorithm, however, wasn't practical, being of non-elementary complexity:

[The procedure described by Hashiguchi] leads to computations that are by far impossible, even for very small examples. For instance, if L is accepted by a 4 state automaton of loop complexity 3 (and with a small 10 element transition monoid), then a very low minorant of the number of languages to be tested with L for equality is:

$\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)}}.$

, Lombardy & Sakarovitch (2002).

The number $10^{10^{10}}$ alone has 10 billion zeros when written down in decimal notation, far larger than the number of atoms in the observable universe.

A much more efficient algorithm than Hashiguchi's procedure was devised by Kirsten in 2005. This algorithm runs, for a given nondeterministic finite automaton as input, within double-exponential space. Yet the resource requirements of this algorithm still greatly exceed the margins of what is considered practically feasible.

This algorithm has been optimized and generalized to trees by Colcombet and Löding in 2008, as part of the theory of regular cost functions. It has been implemented in 2017 in the tool suite Stamina.

Watch videos about Star height problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Star height problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Star height problem

01Families of regular languages with unbounded star height

02Computing the star height of regular languages

Sources and credits

Related topics

Generalized star-height problem

Kleene's algorithm

Deterministic finite automaton