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$.

  • $\begingroup$ 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. $\endgroup$ – Desperado Jul 7 '17 at 17:48
  • $\begingroup$ I am not able to understand 2nd point . $\endgroup$ – Desperado Jul 7 '17 at 17:49
  • $\begingroup$ The first part is actually a subset of the second, so you don't really need it. $\endgroup$ – Yuval Filmus Jul 7 '17 at 17:56
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Jul 7 '17 at 17:58
  • $\begingroup$ As to the level of detail, that's intentional. You'll have to work it out. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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