Generalizing the Kraft-McMillan inequality to restricted languages

Let ℓ ₁,ℓ ₂,...,ℓ _n be a (possibly infinite) sequence of nonnegative integers and Σ some D-ary alphabet. The Kraft-inequality states that ℓ ₁,ℓ ₂,...,ℓ _n are the lengths of the words in some prefix (free) code over Σ if and only if Σ_i=1ⁿD^{-ℓ i}≤1. Furthermore, the code is exhaustive if and only if equality holds. The McMillan inequality states that if ℓ _n are the lengths of the words in some uniquely decipherable code, then the same condition holds. In this paper we examine how the Kraft-McMillan inequality conditions for the existence of a prefix or uniquely decipherable code change when the code is not only required to be prefix but all of the codewords are restricted to belong to a given specific language L. For example, L might be all words that end in a particular pattern or, if Σ is binary, might be all words in which the number of zeros equals the number of ones.