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?
Closure of regular languages under non-contiguous subsequence
automata;finite automata;closure properties
Here are several ways of showing this:Starting with a DFA/NFA for $L$, add $\epsilon$ transitions parallel to all other transitions.Apply the regular substitution that maps $\sigma \in \Sigma$ to $\{\sigma,\epsilon\}$.Starting with a regular expression for $L$, replace all copies of each $\sigma \in \Sigma^*$ by $\epsilon + \sigma$.