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:

    “Women have entered the work force . . . partly to express their feelings of self-worth . . . partly because today many families would not survive without two incomes, partly because they are not at all sure their marriages will last. The day of the husband as permanent meal-ticket is over, a fact most women recognize, however they feel about “women’s liberation.””
    —Robert Neelly Bellah (20th century)

    “[I]n our country economy, letter writing is an hors d’oeuvre. It is no part of the regular routine of the day.”
    —Thomas Jefferson (1743–1826)

    “I am always sorry when any language is lost, because languages are the pedigree of nations.”
    —Samuel Johnson (1709–1784)

    “I must down to the seas again, to the lonely sea and the sky,
    And all I ask is a tall ship and a star to steer her by,”
    —John Masefield (1878–1967)

    “Much more frequent in Hollywood than the emergence of Cinderella is her sudden vanishing. At our party, even in those glowing days, the clock was always striking twelve for someone at the height of greatness; and there was never a prince to fetch her back to the happy scene.”
    —Ben Hecht (1893–1964)