0
$\begingroup$

Consider the following operation on language $L$:

$\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$

I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and proved it by guesing when $y^R$ starts and running it on the inverse DFA. However, if $L$ is a CFL, then $\mathrm{inv}(L)$ is not, and I don't understand why. Can't we just also guess when $y^R$ starts, insert all of it into the stack, then simulate the DFA of $L$ on each item we take out, then continue on $z$ when it's empty?

thanks.

$\endgroup$
0
$\begingroup$

You are right, regular languages are closed under inversion $\mathrm{inv}$, using some proper guesses, or see my answer to a relevant question here.

Context-free languages are not closed under $\mathrm{inv}$. Your intuition does not work. We cannot push $y$ on the stack because it will make the 'real' stack below it inaccessible for the simulation.

Here is a possible counter example. Consider $L = \{ a^nb^nc^md^m \mid m,n\ge 1 \}$. Then try $\mathrm{inv}(L) \cap a^*c^*b^*d^* $.

$\endgroup$

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.