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

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

###### Proposition 1.

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

 $L=L_{1}\cup\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 $\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\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\Sigma^{*}L_{2}$ as a result. This shows that $L\subseteq L_{1}\cup\Sigma^{*}L_{2}$. On the other hand, suppose $u\in L_{1}\cup\Sigma^{*}L_{2}$. If $|u|, then $u\in L_{1}\subseteq L$. If $|u|\geq 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\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 $\Sigma^{*}$ with $|u|\geq 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\Sigma^{*}L_{2}$ and hence $u\in\Sigma^{*}L_{2}$ as well. If $u\in L$, then $u\in\Sigma^{*}L_{2}$, so that $u$ has a suffix $w\in L_{2}$. Since $|w|, $w$ is also a suffix of $v$, and therefore $v\in\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 $\mathscr{D}$ be the family of definite languages, then $\mathscr{D}$ is closed under union and complementation, and therefore any Boolean operations. However, $\mathscr{D}$ is not closed under concatenation, Kleene star, and reversal.

## References

• 1
Title definite language DefiniteLanguage 2013-03-22 18:58:57 2013-03-22 18:58:57 CWoo (3771) CWoo (3771) 10 CWoo (3771) Definition msc 68Q42 msc 68Q45