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 of, families, regular, languages, star and/or height:

    “For those parents from lower-class and minority communities ... [who] have had minimal experience in negotiating dominant, external institutions or have had negative and hostile contact with social service agencies, their initial approaches to the school are often overwhelming and difficult. Not only does the school feel like an alien environment with incomprehensible norms and structures, but the families often do not feel entitled to make demands or force disagreements.”
    —Sara Lawrence Lightfoot (20th century)

    “We are born into them, marry into them, even create them among the people we love. They come large and extended...or small and nuclear. But whatever their size or wherever they live, strong families give us the nurturance and strength we need in order to survive.”
    —Andrea Davis (20th century)

    “They were regular in being gay, they learned little things that are things in being gay, they learned many little things that are things in being gay, they were gay every day, they were regular, they were gay, they were gay the same length of time every day, they were gay, they were quite regularly gay.”
    —Gertrude Stein (1874–1946)

    “The very natural tendency to use terms derived from traditional grammar like verb, noun, adjective, passive voice, in describing languages outside of Indo-European is fraught with grave possibilities of misunderstanding.”
    —Benjamin Lee Whorf (1897–1934)

    “One year
    They sent a million here:
    Here men were drunk like water, burnt like wood.
    The fat of good
    And evil, the breast’s star of hope
    Were rendered into soap.”
    —Randall Jarrell (1914–1965)

    “The lotus’ stem is as long as the depth of water,
    So men’s height is just as great as their inner strength.”
    —Tiruvalluvar (c. 5th century A.D.)