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

Question

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.

Answer 1

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.