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?

| cite | improve this question | | | | |
  • 3
    $\begingroup$ Your construction doesn't depend on $a$, so it cannot be correct. $\endgroup$ – 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$ .

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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