3
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

3
$\begingroup$

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

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

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.

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

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.