0
$\begingroup$

I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible to remove zero or more symbols from w so that just the string x remains. For example, the following strings can all be obtained from 0110 by deleting symbols:

λ, 0, 1, 00, 01, 10, 11, 010, 011, 110, and 0110.

Let Σ = {0, 1} and let A ⊆ Σ ∗ be an arbitrarily chosen regular language.

Define B = {x ∈ Σ ∗ | there exists a string w ∈ A such that x is obtained from w by deleting symbols}.

In words, a string is in B if you can obtain that string by first choosing a string from A and then deleting zero or more symbols from that chosen string. Prove that B is regular.

I'm not able to prove it. Any help would be appreciated.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

Hint 1: As $A$ is regular, it is recognized by finite automata. Try to modify this automata to make it recognize $B$.

Hint 2: Skipping "deleted" symbols might be handled by adding $\epsilon$ - transitions to the original automata in a proper way.

Improve this answer
$\endgroup$
2
$\begingroup$

Use closure properties of regular languages: Apply substitution $\sigma(x) = \{x, \epsilon\}$. This replaces symbols by themselves or nothing.

Improve this answer
$\endgroup$
2
  • $\begingroup$ should I apply this substitution on Every state of my NFA of A language? I don't understand how will it then start accepting language B. Can you please elaborate on it. Sorry, I'm new to automata theory. $\endgroup$
    – jumpy123
    Mar 1, 2020 at 11:48
  • $\begingroup$ @ahmad123, the substitution is applied to the language, i.e. $\sigma(L) = \{\sigma(\alpha) \colon \alpha \in L \}$. It is a theorem that regular langusgrs are closed with respect to substitutions by regular languages for each symbol, and the languagrs here are finite, thus regular. $\endgroup$
    – vonbrand
    Mar 1, 2020 at 16:16
2
$\begingroup$

$A$ has a regular expression. Can you modify the expression so it will express the optional deletion of arbitrary characters?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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