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.
2
$\begingroup$
$\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$
$\endgroup$
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.
answered Apr 16 '17 at 11:40
