2
$\begingroup$

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

enter image description here

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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(.). $\endgroup$ – Kbiir Oct 8 at 19:33
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Steven Oct 9 at 0:14

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.