# Prove that a language is regular

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.

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.
Use closure properties of regular languages: Apply substitution $$\sigma(x) = \{x, \epsilon\}$$. This replaces symbols by themselves or nothing.
• @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. Mar 1, 2020 at 16:16
$$A$$ has a regular expression. Can you modify the expression so it will express the optional deletion of arbitrary characters?