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 $\mathcal{D}$ be the family of definite languages, then $\mathcal{D}$ is closed under union and complementation, and therefore any Boolean operations. However, $\mathcal{D}$ is not closed under concatenation, Kleene star, and reversal.
Remark. In fact, every definite language is locally testable. The converse^{}, however, is not true.
References
- 1 A. Salomaa, Formal Languages^{}, Academic Press, New York (1973).
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 |