# Why does removing all copies of a letter preserve regularity?

Let $$P(a,L)$$ remove every $$a$$ in $$L$$, for example $$P(a,\{ab,aab,aaab,bba\}) = \{b,bb\}.$$

How to show that if $$L$$ is a regular language then $$P(a, L)$$ is also a regular language?

My attempt:

If $$L$$ is regular then $$P(a, L)$$ is regular. Namely, let $$D = (Q,Σ,δ,q_0,F)$$ be a DFA for $$L$$.

Assume every state in $$L$$ is reachable from $$q_0$$. Then we can turn $$D$$ into an NFA $$N$$ for $$P(a, L)$$ by adding a new state $$q_{−1}$$ which becomes the NFA’s start state. For each state $$q ∈ L$$, we add an epsilon transition from $$q_{−1}$$ to $$q$$.

Therefore, define $$N$$ to be $$( L ∪ \{q_{−1}\}, Σ , δ′, q_{−1},F)$$

Is this the correct way to prove it?

• Your construction doesn't depend on $a$, so it cannot be correct. – Yuval Filmus Oct 12 '18 at 3:38

Given an NFA or a DFA (like in your proof, if you want), we replace each arc with letter $$a$$ by $$\varepsilon$$. We obtain an NFA for $$P(a,L)$$. So, $$P(a,L)$$ must be regular.
In details, each trace in the newly constructed NFA can be transformed back to $$a$$-full instance of $$L$$ .