2
$\begingroup$

I'm trying to apply the CFL pumping lemma. And, I've already tried words $a^pb^p$ and $a^pb^pc^p$. Not sure where to go from here.

$\endgroup$
  • $\begingroup$ Hint: Try reversing the language first. $\endgroup$ – PMar Apr 11 '17 at 18:50
  • 2
    $\begingroup$ Sometimes, the Pumping lemma is not strong enough. See our reference question for more approaches. (I guess Ogden's lemma would easily work here.) $\endgroup$ – Raphael Apr 11 '17 at 19:10
  • $\begingroup$ Sometimes, it helps to realize that the pumping lemma also allow deleting the pumped segments: $uv^iwx^iy$ with $i=0$. $\endgroup$ – Hendrik Jan Apr 11 '17 at 19:27
  • $\begingroup$ @PMar Context free languages are not closed under complement. I don't see how that helps. $\endgroup$ – Daniel Apr 12 '17 at 2:22
1
$\begingroup$

Classical pumping works. According to the pumping lemma we can find a segmentation $uvwxy$ such that $uv^iwx^iy$ is in the language for all $i$.

Start with your own suggestion $a^pb^pc^p $.

Three easy steps.

  • Each of the "pumping segments" $v$, $x$ can only be within the boundaries of one the "letter segments" $a^p$, $b^p$, $c^p$.

  • It is not possible to have one of $v$ or $x$ to be in the $a^p$ segment without the other being inside the $b^p$ segment. And the other way around. In that case pump down ($i=0$).

  • Final possibility both $v$ and $x$ are in $c^p$. Pump up.

$\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.