0
$\begingroup$

What I have come across as a definition is - a language $L ⊆ Σ^*$ is said to be definite if and only if $L = E ∪ Σ^*Η$, for some finite languages $E,H ⊆ Σ^*$

Using these questions - Show that every definite language is accepted by a finite automaton

and What are definite languages? How do you formally define them?,

I understand that a definite language is a language where the membership of a string depends on it's last k-symbols only, i.e, those strings sharing the last k-symbols either belong to the language or don't. On these lines, I don't understand how the definition correspond to - $L = E ∪ Σ^*Η$, for some finite languages $E,H ⊆ Σ^*$.

Having an intuitive idea, I am not quite able to get my head around a generic definition of a definite language in Set Builder Form. Could you please give a definition in Set Builder Notation specifically? I also request you to explain why you have defined it in such a manner, as I don't want to be in a situation where I couldn't understand the prior definition being $L = E ∪ Σ^*Η$. I have been going at this for an entire week, now.

$\endgroup$
  • $\begingroup$ I don't understand what your question is. If you whether the sentence "I understand that..." is correct, that was already answered on your other question (cs.stackexchange.com/q/88688/755), so this would be a duplicate. If you're asking for a definition, you already have a definition, and definitions can already be found at the two linked questions, so this would again be a duplicate. Please edit your question to clarify exactly what your question is. Finally, there is no answer to "why?"; a definition is a definition. Also, please ask only one question per post. $\endgroup$ – D.W. Mar 1 '18 at 0:00
  • $\begingroup$ @D.W The aim of my question is that I lack the knowledge or capability to convert an existing definition of a definite language into Set Builder Form, even though I seem to be understanding the concept, and hence require help in knowing how to define a generic definite language in Set Builder Notation. $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 0:20
  • $\begingroup$ @D.W, first of all, it is not a duplicate, as that question addresses the understanding of the "concept" of definite languages and understanding its definition, not defining it in "Set Builder Form". I had answered it myself, after I felt I had grasped some understanding, prior to my account being deleted. Please do read my question properly for the technical detail being asked in regards to the definition. I had not asked for a definition of the concept, as I had already mentioned in my answer the understanding of the concept I had, from those two questions. $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 0:24
  • $\begingroup$ @D.W Second of all, my account was deleted, and I lost access to my previous two questions, with (cs.stackexchange.com/q/88688/755) being one of them. :) I had instructed my classmate to analyse an answer given to the same question, who, without my permission, went on to post a homework question given to us, and just copied and pasted it word by word, which was criticised by you in like 2 comments especially for not crediting sources, post which my account was just randomly deleted, haha. :) Hence I had to ask another question regarding the same concept, after creating a new account. :) $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 0:28
2
$\begingroup$

In set-builder notation, it's just $E\cup \{vw\mid v\in\Sigma^*\text{ and }w\in H\}$.

So, why is this the same thing as "Languages that can be recognized by the last $k$ characters of the string"

One direction is fairly simple. If $L$ can be recognized by looking at the last $k$ characters, then there must be some set $H$ of length-$k$ strings such that, if the last $k$ characters form a string in $H$, you accept the string, and if they form a string not in $H$, you reject. Furthermore, there may be some strings that you accept even though they have fewer than $k$ characters: this set is $E$.

The other direction is a little more complex. Suppose that $L = E\cup\Sigma^*H$ for some finite $E$ and $H$. We need to show that there is some $k$ and sets $X\subseteq\Sigma^{<k}$ and $Y\subseteq \Sigma^k$ such that $L=X \cup\Sigma^*Y$. Note that this is different from the hypothesis that $L=E\cup\Sigma^*H$ because it's more specific: $E$ and $H$ can be any finite sets of strings, whereas $X$ contains only strings of length less than $k$ and $Y$ contains only strings of length exactly $k$.

The solution is to take $k$ to be whichever is the larger of:

  • the length of the longest string in $H$;
  • one plus the length of the longest string in $E$.

(Since both $E$ and $H$ are finite, each has a longest string, or several longest strings of the same length.)

We start by taking $X=E$, which we're allowed to do because every string in $E$ has length strictly less than $k$. Now, consider some string $h=h_1\dots h_\ell\in H$. We have $\ell\leq k$ by the choice of $k$. If $\ell=k$, we're happy: just add $h$ to $Y$. Now suppose that $\ell<k$. If a string ends with $h$, then either it has length less than $k$ or it has length at least $k$ and its last $k$ characters are $a_1\dots a_{k-\ell}h_1\dots h_\ell$ for some $a_1, \dots, a_{k-\ell}\in\Sigma$. Therefore, we add to $X$ all strings of length less than $k$ that end with $h$, and we add to $Y$ all strings of length exactly $k$ that end with $h$. And we repeat this for every $h\in H$.

I've explained how to construct $X$ and $Y$. I won't write out their formal definitions as sets because those definitions are so full of notation that they're not enlightening.

$\endgroup$
  • $\begingroup$ Could you explain how? Why is it a union of two sets? How is this definition the same as saying that the language has a membership criteria depending on the last k symbols of a string? $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 8:28
  • $\begingroup$ Consider the language $ \textit{L = { x : x is a string in binary ending with 000}}$. This language is definite as the membership criteria for its strings is that all strings should share the 3-suffix 000, right? How would you express this in terms of the definition you have stated? $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 8:32
  • $\begingroup$ You asked for the definition to be phrased in set-builder notation, so I did that. It's a union of two sets because that's what the definition in the question says it is. All the other stuff wasn't in your question. Your example language is $E=\emptyset$, $H=\{000\}$. $\endgroup$ – David Richerby Mar 1 '18 at 8:35
  • $\begingroup$ Alright, thank you for your input. I have accordingly added more clarity to my question as well. $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 8:46
  • $\begingroup$ "Furthermore, there may be some strings that you accept even though they have fewer than k characters", I don't understand this reasoning. How does a definite language accept strings with less than k symbols? The criteria in itself is the fact that the minimum length of a string in the language should be greater than or equal to k, only after which it is recognised by inspecting just the last k symbols, right? So a string with less than k symbols shouldn't be considered in the language, right? $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.