I have a question in my homework that deals with the concept of a definite language. The question defines a definite language as follows -
"A language L is definite if there is some k(> 0) such that for any string w, whether w ∈ L depends on the last k symbols of w." I'm supposed to do the following -
a) Rewrite this definition formally
b) Prove that every definite language is accepted by a finite automaton
c) Give an example of two definite languages L1 and L2 such that L1.L2 is not definite.
I'm breaking my head over the definition given in the question. In-depth google searches lead me to a few google books and this is what I came across -
- Theory of Automata, Arto Salomaa :
Definite languages are completely characterized by the final subwords of a given length k of a string. The behaviour of definite automata depends exclusively on the latest k input letters for some k. Thus, the behaviour is independent of inputs which have occurred at sufficiently remote past moments.
- Role of Theory in Computer Science: (edited by Konstantinidis Stavros, Moreira Nelma, Reis Rogerio)
Whether or not a word belongs to a given definite language can be determined by inspecting the last k symbols, where k is a constant only depending on the language. In particular, two words whose length exceed k having the same suffix either both belong to the language or both do not.
More precisely, a language L ⊆ Σ* is said to be definite if and only if L = E ∪ Σ*Η, for some finite languages E,H ⊆ Σ*.
- Theory of Formal Languages with Applications by Dan Simocivi, Richard L Tenney:
Τhis alternative definition was given by Perles, Rabin and Shamir.
A language L over the alphabet A is weakly k-definite if x ε L holds for a word x with |x| ≥ k if and only if the suffix of length k of x belongs to the language L.
For k ε Ν and k ≥ 1, a language L is k-definite if L is weakly k-definite, but it is not (k-1)-definite. A language is definite if it is k-definite for some k ε Ν.
Even after reading all this, I am not able to understand anything regarding the concept of a definite language. How can you precisely define a language to be definite when you don't know what the dependency on the last k symbols of ω is? Shouldn't the definition "depends on the last k symbols" be more clear? What can you quantify as a dependency on the last k symbols, to decide whether ω will belong to L? It doesn't make sense to me. Could you help me in getting a better, clearer, simpler understanding of this? Could you please give some examples, while explaining the concept?