Classifications of dense languages

Abstract

Let X be a finite alphabet containing more than one letter. A dense language over X is a language containing a disjunctive language. A language L is an n-dense language if for any distinct n words w(1), w(2),..., w(n) is an element of X+, there exist two words u, v is an element of X* such that uw(1)v, uw(2)v,... uw(n)v is an element of L. In this paper we classify dense languages into strict n- dense languages and study some of their algebraic properties. We show that for each n >= 0, the n- dense language exists. For an n- dense language L, n not equal 1, the language L boolean AND Q is a dense language, where Q is the set of all primitive words over X. Moreover, for a given n >= 1, the language L is such that L boolean AND Q is an element of D-n(X), then L is an element of D-m( X) for some m, n <= m <= 2n+1. Characterizations on 0-dense languages and n- dense languages are obtained. It is true that for any dense language L, there exist w(1) not equal w(2) is an element of X+ such that uw(1)v, uw(2)v is an element of L for some u, v is an element of X*. We show that every n- dense language, n >= 0, can be split into disjoint union of infinitely many n- dense languages.