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:

    “The ideal of the self-sufficient American family is a myth, dangerous because most families, especially affluent families, do in fact make use of a range of services to survive. Families needing one or another kind of help are not morally deficient; most families do need assistance at one time or another.”
    —Joseph Featherstone (20th century)

    “While you’re playing cards with a regular guy or having a bite to eat with him, he seems a peaceable, good-humoured and not entirely dense person. But just begin a conversation with him about something inedible, politics or science, for instance, and he ends up in a deadend or starts in on such an obtuse and base philosophy that you can only wave your hand and leave.”
    —Anton Pavlovich Chekhov (1860–1904)

    “It is time for dead languages to be quiet.”
    —Natalie Clifford Barney (1876–1972)

    “The flattering, if arbitrary, label, First Lady of the Theatre, takes its toll. The demands are great, not only in energy but eventually in dramatic focus. It is difficult, if not impossible, for a star to occupy an inch of space without bursting seams, cramping everyone else’s style and unbalancing a play. No matter how self-effacing a famous player may be, he makes an entrance as a casual neighbor and the audience interest shifts to the house next door.”
    —Helen Hayes (1900–1993)

    “The most stupendous scenery ceases to be sublime when it becomes distinct, or in other words limited, and the imagination is no longer encouraged to exaggerate it. The actual height and breadth of a mountain or a waterfall are always ridiculously small; they are the imagined only that content us.”
    —Henry David Thoreau (1817–1862)