The dot-depth hierarchy of star-free languages is infinite

摘要

Let A be a finite alphabet and A∗ the free monoid generated by A. A language is any subset of A∗. Assume that all the languages of the form {a}, where a is either the empty word or a letter in A, are given. Close this basic family of languages under Boolean operations; let B(0) be the resulting Boolean algebra of languages. Next, close B(0) under concatenation and then close the resulting family under Boolean operations. Call this new Boolean algebra B(1), etc. The sequence B(0), B(1),…, Bk,… of Boolean algebras is called the dot-depth hierarchy. The union of all these Boolean algebras is the family A of star-free or aperiodic languages which is the same as the family of noncounting regular languages. Over an alphabet of one letter the hierarchy is finite; in fact, B(2) = B(1). We show in this paper that the hierarchy is infinite for any alphabet with two or more letters.