definite language

A language 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 $\mathrm{\Sigma }$. Then $L$ is definite if there is a non-negative integer $k$ such that for any word $u$ over $\mathrm{\Sigma }$ with $|u|\ge k$, its suffix $v$ of length $k$ is in $L$ iff $u$ is in $L$.

Note that if $k=0$, then $L$ is either ${\mathrm{\Sigma }}^{*}$ or $\mathrm{\varnothing }$.

A definite language has the following characterization:

Proposition 1.

$L$ is definite iff there are finite languages $L_{\mathrm{1}}$ and $L_{\mathrm{2}}$ such that

$$L=L_1\cup {\mathrm{\Sigma }}^{*}{L}_2.$$

Proof.

Suppose first that $L$ is definite. Let $L_1$ be the subset of $L$ containing all words with length less than $k$ and $L_2$ 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$, $L_1$ is either $\{\lambda \}$ or $\mathrm{\varnothing }$, depending on whether or not $\lambda \in L$. In any case, $L_1$ and $L_2$ are both finite. We verify that $L=L_1\cup {\mathrm{\Sigma }}^{*}{L}_2$. If $u\in L$ and $u$ has length less than $k$, then $u\in L_1$. 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 $L_2$. Therefore $u\in {\mathrm{\Sigma }}^{*}{L}_2$ as a result. This shows that $L\subseteq L_1\cup {\mathrm{\Sigma }}^{*}{L}_2$. On the other hand, suppose $u\in L_1\cup {\mathrm{\Sigma }}^{*}{L}_2$. If , then $u\in L_1\subseteq L$. If $|u|\ge k$, write $u=wv$ where $v$ is the suffix with length $k$. Then $v\in L_2$, which means that $u\in L$ since $L$ is definite.

Now suppose $L=L_1\cup {\mathrm{\Sigma }}^{*}{L}_2$ with $L_1,L_2$ finite. Let $k$ be the maximum of lengths of words in $L_1\cup L_2$, plus $1$. $k$ is well-defined since $L_1\cup L_2$ is finite. Suppose $u$ is a word in ${\mathrm{\Sigma }}^{*}$ with $|u|\ge k$. Then $u\notin L_1$. Let $v$ be the suffix of $u$ with $|v|=k$. Then $v\notin L_1$ likewise. If $v\in L$, then $v\in {\mathrm{\Sigma }}^{*}{L}_2$ and hence $u\in {\mathrm{\Sigma }}^{*}{L}_2$ as well. If $u\in L$, then $u\in {\mathrm{\Sigma }}^{*}{L}_2$, so that $u$ has a suffix $w\in L_2$. Since , $w$ is also a suffix of $v$, and therefore $v\in {\mathrm{\Sigma }}^{*}{L}_2\subseteq L$ 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 converse, however, is not true.