# For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$. The subsequence is proper if $k < n$ and $k > 0$.

With this definition given, a homework problem asks the following: Suppose $L$ and $L_1$ are languages, and define $L \diamond L_1$ to be the set $\{x \in L : \text{no string } x' \in L_1 \text{ is a proper subsequence of } x\}$. If both $L$ and $L_1$ are regular, does it follow that $L \diamond L_1$ is regular? Justify your answer.

I've attempted to construct an NFA that would recognize $L \diamond L_1$, but this went nowhere, as things soon got overly complicated. Any ideas or suggestions?

Hint: Let $L_2$ be the set of supersequences of words in $L_1$, i.e.,
$$L_2 = \{x \in \Sigma^* : \exists y \in L_1 . \text{y is a subsequence of x}\}.$$
If $L_1$ is regular, what can you say about $L_2$? Is it regular? If you have a NFA for $L_1$, can you construct a NFA that would recognize $L_2$?
If you are not sure, try some examples of regular languages $L_1$, and work out $L_2$ looks like for each example.
• I've taken your advice. So suppose, for example, that $L_1 = 0^*1^*$. It seems that the corresponding set of supersequences, $L_2$, could be described by the regular expression $\Sigma^*0^*\Sigma^*1^*\Sigma^*$. Thus, it seems, in general, that we can "insert" whatever we like between, before, or after, the characters of a string in $L_1$, so long as the relative ordering of these characters is preserved. Sep 13 '14 at 22:41