The Generalized Star-Height Problem.pdf

The Generalized Star-Height Problem Jonah Sherman May 8, 2007 1 Introduction The minimal number of nested Kleene stars required in a regular expression representing a language provides a simple complexity measure on the regular languages. For restricted regular expressions in which complementation is not allowed, much is known about the measure. In particular, Eggan(1963) showed that for any n, there is a language of star-height n[1]. Hashiguchi(1983) then gave a method of computing the star-height of an arbitrary regular language[2]. However, when one allows complementation as a regular operation, one ob- tains the generalized regular expressions. In that case, not much is known about the problem. There is no known decision procedure to decide if a language has a particular star-height. In fact, it is not even known whether there is a lan- guage of star-height 2. We present some of the known results on the star-height problem, and describe some ideas that may lead the path to a solution. 2 Definitions We begin by defining the generalized regular expressions over some alphabet Σ, recursively: ? ?, ε are gres ? For all σ ∈ Σ, σ is a gre ? If A,B are gres, then A ∪B and AB are gres ? If A is a gre, A? and A are gres The complement operator is why these expressions are called “generalized”. We then define the star-height of a gre, to be the number of nested Kleene stars it contains. Formally, ? h(?) = h(ε) = h(σ) = 0 for all σ ∈ Σ ? h(A ∪B) = h(AB) = max{h(A), h(B)} ? h(A) = h(A) 1 ? h(A?) = h(A) + 1. Then, for each language A, define the star-height of the language A, |A|, to be the minimum over all regular expressions E representing A of h(E). |A| = min E h(E) We can now state the actual problem. The generalized star-height problem is the question “is there an algorithm to determine the star-height of a regular language?”. The star-height 2 problem asks “is there a language of star-height 2?”. Since we are exclusively concerned with the generalized star-height, we sh