definite language

A languagePlanetmathPlanetmath is definite if the determination of whether a word belongs to the language completely depends on its suffix of a fixed length. Formally,

Definition. Let L be a language over an alphabet Σ. Then L is definite if there is a non-negative integer k such that for any word u over Σ with |u|k, its suffix v of length k is in L iff u is in L.

Note that if k=0, then L is either Σ* or .

A definite language has the following characterizationMathworldPlanetmath:

Proposition 1.

L is definite iff there are finite languages L1 and L2 such that


Suppose first that L is definite. Let L1 be the subset of L containing all words with length less than k and L2 the subset of L containing all words of length k. The case when k=0 is already mentioned in the note above. If k=1, L1 is either {λ} or , depending on whether or not λL. In any case, L1 and L2 are both finite. We verify that L=L1Σ*L2. If uL and u has length less than k, then uL1. Otherwise, it has length at least k. By the definiteness of L, its suffix v of length k is in L, and thus is in L2. Therefore uΣ*L2 as a result. This shows that LL1Σ*L2. On the other hand, suppose uL1Σ*L2. If |u|<k, then uL1L. If |u|k, write u=wv where v is the suffix with length k. Then vL2, which means that uL since L is definite.

Now suppose L=L1Σ*L2 with L1,L2 finite. Let k be the maximum of lengths of words in L1L2, plus 1. k is well-defined since L1L2 is finite. Suppose u is a word in Σ* with |u|k. Then uL1. Let v be the suffix of u with |v|=k. Then vL1 likewise. If vL, then vΣ*L2 and hence uΣ*L2 as well. If uL, then uΣ*L2, so that u has a suffix wL2. Since |w|<k, w is also a suffix of v, and therefore vΣ*L2L as a result. This shows that L is definite. ∎

From this characterization, we see that finite languages are special cases of definite languages. We also see that

Corollary 1.

Every definite language is a regular language.

With regard to the closure properties of definite languages, we have the following: let 𝒟 be the family of definite languages, then 𝒟 is closed under union and complementation, and therefore any Boolean operations. However, 𝒟 is not closed under concatenation, Kleene star, and reversal.

Remark. In fact, every definite language is locally testable. The converseMathworldPlanetmath, however, is not true.


Title definite language
Canonical name DefiniteLanguage
Date of creation 2013-03-22 18:58:57
Last modified on 2013-03-22 18:58:57
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 68Q42
Classification msc 68Q45