1
$\begingroup$

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 -

  1. 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.

  1. 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 ⊆ Σ*.

  1. 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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Are you familiar with the Myhill-Nerode theorem? It may hold some inspiration. $\endgroup$
    – Raphael
    Commented Feb 27, 2018 at 20:57
  • $\begingroup$ I think you are overthinking this. All it means is that only the last k symbols in the string matter. All the rest of them could be replaced with anything (or even nothing) without changing the membership of the string in the language. $\endgroup$
    – rici
    Commented Feb 28, 2018 at 0:21
  • $\begingroup$ @rici Yes after some thought I think I understand. Considering that the membership solely depends on the last k symbols, a language like - L = { x1010 : x ε {0,1}*} , should qualify as a definite language, since the condition - the last 4 (k) symbols of the string are to be 1010, defines the membership of the overall string, to L. But what is the generalisation of this specific example, or the intuitive idea of definite languages? What is the formal definition in set builder form? $\endgroup$
    – user85055
    Commented Feb 28, 2018 at 12:05
  • $\begingroup$ @Raphael Yes, I am. I realise I can use it to prove if definite languages are regular or the fact that every definite language can be accepted by a finite automaton, but before I do so, I'm not able to get hands on the part where I define a generic definite language in set builder form. $\endgroup$
    – user85055
    Commented Feb 28, 2018 at 12:06
  • $\begingroup$ I was thinking the the way the Myhill-Nerode theorem is formalized could inspire how to formalize this one. $\endgroup$
    – Raphael
    Commented Feb 28, 2018 at 12:50

2 Answers 2

Reset to default
1
$\begingroup$

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.

There is of course room for interpretation here. Assuming they mean "[it] only depends on the last $k$ symbols of $w$", here's a slightly more precise rephrasing:

A language L is definite if there is some $k$ so that all words that share the same $k$-suffix are either in or not in the language.

Try to work from here.

Improve this answer
$\endgroup$
0
0
$\begingroup$

Okay so this is what I managed to understand. As @rici mentioned, I was definitely (no pun intended) overthinking this concept.

Using @Raphael's suggested definition -

A language L is definite if there is some k so that all words that share the same k-suffix are either in or not in the language.

With some thinking, I came up with an easy example of a language whose membership criteria is based on a condition on the last k symbols of its string, such as -

$$L = \{ \text{x000} \mid \text{x ∈ Σ$^*$} \}, where \ Σ=\{0,1\} $$

The dependency here is - the last 3 symbols (i.e k=3 in this case), should be 000. Hence, all strings that share the same 3-suffix (000 in this case), are in the language.

Αll those that share any other 3-suffix from Σ$^3$ apart from 000,

$i.e$, from Σ$^3$ - {000} = {001,100,101,111,010,110,011}, are not in L. Τhis concurs to the said definition. Generalizing this example, we arrive at the following -

$$ \textit{A language L is definite, if for some k > 0, wu ∈ L ⇔ u ∈ L } \forall \textit{ w ∈ } \Sigma^* \textit{ and u ∈ } \Sigma^k. $$

Therefore, L can be defined as -

$$ L = \{\ { wu ∈ L \mid u ∈ L\ } \forall \textit{ w ∈ } \Sigma^* \textit{and u ∈ } \Sigma^k \}$$

To prove that definite languages are regular, we need to prove that there are finitely many equivalence classes using the Myhill-Nerode theorem. If Σ is finite, of course, definite languages are obviously regular.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Looks reasonable to me! $\endgroup$
    – Raphael
    Commented Feb 28, 2018 at 16:07
  • $\begingroup$ (It is a little strange to define the language $L$ in terms of itself.) But there is a small point that is not covered here: membership of strings shorter than $k$ is "free", any subset of $\Sigma^{< k}$ can be in the language. $\endgroup$
    – Hendrik Jan
    Commented Feb 28, 2018 at 18:38
  • $\begingroup$ @HendrikJan Now that you've mentioned it, yes, I have a weird feeling about my definition. I should probably redefine it with more thought. And wow. I did not think of that. Could you please elaborate on how it is valid for a string having less than k symbols to be part of the language? Considering that the membership criteria depends on the last k symbols of a string, if a string has less than k symbols, how does it make sense that they can be part of the language? Shouldn't the base criteria for membership be the fact that every string's length should be greater than or equal to k? $\endgroup$
    – user85055
    Commented Feb 28, 2018 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.