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:

    “Families need families. Parents need to be parented. Grandparents, aunts, and uncles are back in fashion because they are necessary. Stresses on many families are out of proportion to anything two parents can handle.”
    —T. Berry Brazelton (20th century)

    “This is the frost coming out of the ground; this is Spring. It precedes the green and flowery spring, as mythology precedes regular poetry. I know of nothing more purgative of winter fumes and indigestions. It convinces me that Earth is still in her swaddling-clothes, and stretches forth baby fingers on every side.”
    —Henry David Thoreau (1817–1862)

    “People in places many of us never heard of, whose names we can’t pronounce or even spell, are speaking up for themselves. They speak in languages we once classified as “exotic” but whose mastery is now essential for our diplomats and businessmen. But what they say is very much the same the world over. They want a decent standard of living. They want human dignity and a voice in their own futures. They want their children to grow up strong and healthy and free.”
    —Hubert H. Humphrey (1911–1978)

    “Between us two it’s not a star at all.
    It’s a new patented electric light,
    Put up on trial by that Jerseyite
    So much is being now expected of....”
    —Robert Frost (1874–1963)

    “To say more than human things with human voice,
    That cannot be; to say human things with more
    Than human voice, that, also, cannot be;
    To speak humanly from the height or from the depth
    Of human things, that is acutest speech.”
    —Wallace Stevens (1879–1955)