# Closure of regular languages under non-contiguous subsequence

Suppose there is a language $L$ on alphabet $Σ$. Now consider the language

$$S(L) = \{x : wxy ∈ L, w, y ∈ Σ^*\} ∪ \{x : w ∈ L,\text{ and x is a subsequence of w}\}.$$

How to prove that if $L$ is regular then $S(L)$ is also regular?

For first part I think if there is a DFA that accepts $wxy$ then there is a DFA that accepts $x$. For second part I have no clue. Can anyone shed some light on this or can provide a formal proof for this?

Here are several ways of showing this:

1. Starting with a DFA/NFA for $L$, add $\epsilon$ transitions parallel to all other transitions.

2. Apply the regular substitution that maps $\sigma \in \Sigma$ to $\{\sigma,\epsilon\}$.

3. Starting with a regular expression for $L$, replace all copies of each $\sigma \in \Sigma^*$ by $\epsilon + \sigma$.

• I think a little more explanation is required . Is your solution is for second part only ? What do you mean by adding transitions parallel to other transitions ? Whqt substitution you are talking about ? I am understanding it a little bit but not completely. – Desperado Jul 7 '17 at 17:48
• I am not able to understand 2nd point . – Desperado Jul 7 '17 at 17:49
• The first part is actually a subset of the second, so you don't really need it. – Yuval Filmus Jul 7 '17 at 17:56
• As for the second point, the regular languages are closed under regular substitution. A regular substitution is a mapping $s\colon \Sigma \to 2^{\Delta^*}$ in which $s(\sigma)$ is regular for all $\sigma \in \Sigma$. We extend $s$ to words by concatenation, and to languages by $s(L) = \bigcup_{w \in L} s(w)$. – Yuval Filmus Jul 7 '17 at 17:58
• As to the level of detail, that's intentional. You'll have to work it out. – Yuval Filmus Jul 7 '17 at 17:58

Given a DFA $M$ for $L$ create a new NFA with $\epsilon$-moves $M'$ by adding a new transition $\delta(q_i, \epsilon) = q_j$ for each existing transition $\delta(q_i,a) = q_j$ for some symbol $a \in \Sigma$.

Now for example if $w = abaabab$ is accepted by $M$ and $u = aab$ is a subsequence of $w$, then $u$ can be written as $a \epsilon \epsilon ab \epsilon \epsilon$ which is accepted by $M'$ according to the new NFA rules.

• Thanks as I am not very good with this, your explanation is very good and simple. – Desperado Jul 7 '17 at 18:38