0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – David Smith
    Commented Sep 13, 2014 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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