Star Height Problem - Families of Regular Languages With Unbounded Star Height

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 (1963) are described in the following, by means of giving a regular expression for each language:

\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}

The construction principle for these expressions is that expression is obtained by concatenating two copies of, 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 there is no equivalent regular expression of star height less than n; a proof is given in (Eggan 1963).

However, Eggan's examples use a large alphabet, of size 2n-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 & Schützenberger (1966). Their examples can be described by an inductively defined family of regular expressions over the binary alphabet as follows–cf. Salomaa (1981):

\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}

Again, a rigorous proof is needed for the fact that does not admit an equivalent regular expression of lower star height. Proofs are given by (Dejean & Schützenberger 1966) and by (Salomaa 1981).

Read more about this topic:  Star Height Problem

Famous quotes containing the words families, regular, languages, star and/or height:

    “Children from humble families must be taught how to command just as other children must be taught how to obey.”
    —Friedrich Nietzsche (1844–1900)

    “It was inspiriting to hear the regular dip of the paddles, as if they were our fins or flippers, and to realize that we were at length fairly embarked. We who had felt strangely as stage-passengers and tavern-lodgers were suddenly naturalized there and presented with the freedom of the lakes and woods.”
    —Henry David Thoreau (1817–1862)

    “The less sophisticated of my forbears avoided foreigners at all costs, for the very good reason that, in their circles, speaking in tongues was commonly a prelude to snake handling. The more tolerant among us regarded foreign languages as a kind of speech impediment that could be overcome by willpower.”
    —Barbara Ehrenreich (b. 1941)

    “Far star that tickles for me my sensitive plate
    And fries a couple of ebon atoms white....”
    —Robert Frost (1874–1963)

    “The prevalence of suicide, without doubt, is a test of height in civilization; it means that the population is winding up its nervous and intellectual system to the utmost point of tension and that sometimes it snaps.”
    —Havelock Ellis (1859–1939)