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,
Note that if , then is either or .
is definite iff there are finite languages and such that
Suppose first that is definite. Let be the subset of containing all words with length less than and the subset of containing all words of length . The case when is already mentioned in the note above. If , is either or , depending on whether or not . In any case, and are both finite. We verify that . If and has length less than , then . Otherwise, it has length at least . By the definiteness of , its suffix of length is in , and thus is in . Therefore as a result. This shows that . On the other hand, suppose . If , then . If , write where is the suffix with length . Then , which means that since is definite.
Now suppose with finite. Let be the maximum of lengths of words in , plus . is well-defined since is finite. Suppose is a word in with . Then . Let be the suffix of with . Then likewise. If , then and hence as well. If , then , so that has a suffix . Since , is also a suffix of , and therefore as a result. This shows that is definite. ∎
From this characterization, we see that finite languages are special cases of definite languages. We also see that
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.
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Date of creation||2013-03-22 18:58:57|
|Last modified on||2013-03-22 18:58:57|
|Last modified by||CWoo (3771)|