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?
For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?
formal languages;regular languages;closure properties
Since this is a homework question, I'll just give a hint.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.