Star height problem

Families 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{aligned} e_{1} & = a_{1}^{*} \\ e_{2} & = {(a_{1}^{*} a_{2}^{*} a_{3})}^{*} \\ e_{3} & = {({(a_{1}^{*} a_{2}^{*} a_{3})}^{*} {(a_{4}^{*} a_{5}^{*} a_{6})}^{*} a_{7})}^{*} \\ e_{4} & = {({({(a_{1}^{*} a_{2}^{*} a_{3})}^{*} {(a_{4}^{*} a_{5}^{*} a_{6})}^{*} a_{7})}^{*} {({(a_{8}^{*} a_{9}^{*} a_{10})}^{*} {(a_{11}^{*} a_{12}^{*} a_{13})}^{*} a_{14})}^{*} a_{15})}^{*} \end{aligned}

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{aligned} e_{1} & = (a b)^{*} \\ e_{2} & = {(a a (a b)^{*} b b (a b)^{*})}^{*} \\ e_{3} & = {(a a a a {(a a (a b)^{*} b b (a b)^{*})}^{*} b b b b {(a a (a b)^{*} b b (a b)^{*})}^{*})}^{*} \\ \dots \\ e_{n + 1} & = (\underset{2^{n}}{\underset{⏟}{a \dots a}} \cdot e_{n} \cdot \underset{2^{n}}{\underset{⏟}{b \dots b}} \cdot e_{n})^{*} \end{aligned}

One more chapter is free with a Lably account.

Families of regular languages with unbounded star height

Computing the star height of regular languages

More in Computing and communication