# show that if L is a regular, then drop(L) is a regular

I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof.

I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I feel something is missing.

I also tried to prove it by showing that w1 ∈ L1, w2 ∈ L2, …, wk ∈ Lk and a ∈ La.

thus Language L can be represented by:

L = L1*La*L2*La*…LaLk If L is regular then L1,L2,...,Lk and La are also regular.

Finally drop(L) can be presented as follow: drop(L) = L1*L2*…*Lk, since L1,L2,...Lk are regular is drop(L) (because we know that it is closed under concatenation)

I feel that there are some notation that I am not using correctly, I don't know why I feel something is missing but can't figure it out.

## 1 Answer

I'm not sure what $$L1, \dots, Lk$$ are since you did not define them. The easiest way is probably that of starting with a DFA for $$L$$ and constructing a NFA for $$drop(L)$$ (hint in the spoiler below).

Replace all transitions labelled with "a" in the DFA for $$L$$ with $$\epsilon$$-transitions in the NFA for $$drop(L)$$.

Then it should be easy to show that:

• If $$w \in drop(L)$$ then the NFA accepts $$w$$: use the definition of the function $$drop$$ to conclude that there must be a suitable word $$w' \in L$$. Start from an accepting path $$\pi$$ for $$w'$$ in the DFA for $$L$$ and modify $$\pi$$ to be an accepting path for $$w$$ in the NFA for $$drop(L)$$.
• If the NFA accepts a word $$w$$ then $$w \in drop(L)$$: look at an accepting path in the NFA for $$drop(L)$$ and use it construct a word $$w'$$ that is accepted by the DFA for $$L$$. Use the fact that you just proved that $$w' \in L$$ and the definition of the function $$drop$$ to conclude that $$w$$ must belong to $$drop(L)$$.

I'm purposefully being a bit vague on the details, so I don't completely give away the solution. Comment if you need more help.

• Isn't a sufficient proof to show that we can construct an NFA for drop(L)? I don't really understand the definition of drop(.). – Kbiir Oct 8 '19 at 19:33
• I used $drop(\cdot)$ to refer to the symbol $drop$ while stressing that it is a function. It just means "the function named 'drop'", where no particular argument is specified. As you say, the only thing that needs to be done is to construct a NFA for $drop(L)$ (and to formally show that such a NFA accepts a word $w$ iff $w \in drop(L)$). I have edited the answer to remove the notation $drop(\cdot)$. – Steven Oct 9 '19 at 0:14