patternMinor
Closure of regular languages under non-contiguous subsequence
Viewed 0 times
nonlanguagesregularsubsequenceundercontiguousclosure
Problem
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?
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?
Solution
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$.
-
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$.
Context
StackExchange Computer Science Q#77672, answer score: 3
Revisions (0)
No revisions yet.