Star height problem

The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required? The problem was raised by . 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 are described in the following, by means of giving a regular expression for each language: 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 . 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 . Their examples can be described by an inductively defined family of regular expressions over the binary alphabet as follows–cf. : 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 and by . In contrast, the second question turned out to be much more difficult, and the question became a famous open problem in formal language theory for over two decades . For years, there was only little progress. The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be decidable .