Editing Star height problem (section)

==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 ''h''(''L'') 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:

:<math>\begin{alignat}{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{alignat}
</math>

The construction principle for these expressions is that expression <math>e_{n+1}</math> is obtained by concatenating two copies of <math>e_n</math>, 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. The remaining, more difficult part, is to prove that for <math>e_n</math> there is no equivalent regular expression of star height less than ''n''; a proof is given in {{harvtxt|Eggan|1963}}.

However, Eggan's examples use a large [[Alphabet (computer science)|alphabet]], of size 2<sup>''n''</sup>-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.{{sfn|Dejean|Schützenberger|1966}}
Their examples can be described by an [[inductive definition|inductively defined]] family of regular expressions over the binary alphabet <math>\{a,b\}</math> as follows&ndash;cf. {{harvtxt|Salomaa|1981}}:
 
:<math>\begin{alignat}{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{alignat}
</math>

Again, a rigorous proof is needed for the fact that <math>e_n</math> does not admit an equivalent regular expression of lower star height. Proofs are given by {{harvtxt|Dejean|Schützenberger|1966}} and by {{harvtxt|Salomaa|1981}}.