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.

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