|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
definite language
|
(Definition)
|
|
|
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|\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 $\Sigma^*$ or $\varnothing$ .
A definite language has the following characterization:
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 $\lbrace \lambda \rbrace$ 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|<k$ , 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 \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|\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
\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|<k$ , $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
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.
- 1
- A. Salomaa, Formal Languages, Academic Press, New York (1973).
|
"definite language" is owned by CWoo.
|
|
(view preamble | get metadata)
Cross-references: converse, locally testable, reversal, Kleene star, concatenation, operations, Boolean, union, closed under, closure properties, regular language, well-defined, plus, finite, subset, finite languages, characterization, iff, integer, alphabet, length, fixed, belongs, language
There is 1 reference to this entry.
This is version 7 of definite language, born on 2009-07-27, modified 2009-07-28.
Object id is 11847, canonical name is DefiniteLanguage.
Accessed 299 times total.
Classification:
| AMS MSC: | 68Q45 (Computer science :: Theory of computing :: Formal languages and automata) | | | 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
