# Can someone give a generic definition of any Definite Language in set builder notation?

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

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.

• @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. – Vishhvak Srinivasan Mar 1 '18 at 0:20
• @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. :) – Vishhvak Srinivasan Mar 1 '18 at 0:28

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.

• 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? – Vishhvak Srinivasan Mar 1 '18 at 8:28
• 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? – Vishhvak Srinivasan Mar 1 '18 at 8:32
• 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\}$. – David Richerby Mar 1 '18 at 8:35
• Alright, thank you for your input. I have accordingly added more clarity to my question as well. – Vishhvak Srinivasan Mar 1 '18 at 8:46
• "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? – Vishhvak Srinivasan Mar 1 '18 at 12:05