A Stronger Pumping Lemma for Context-Free Languages

Here we prove a slightly stronger version of the pumping lemma for context-free languages, wherein both the parts that are pumped can be assumed to be non-empty. The trick here is to analyze the parse tree generated in the usual proof, and to make it even taller to avoid the case where one of the parts can be empty.

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[EasyTheory]

Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are in the video description. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Simone Glinz, Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su

[jrodonthebeat]

Bro you single handedly helped me pass my computational models class. I went on a binge for all your videos on the theory of computation a week before my finals and it taught it everything I needed to know. Stopped when Turing machines came up cuz it wasn’t a big final topic, but now I kinda wanna go back and finish that up and learn it

[codeneed]

but still the three As can be on the left most path. I dont understand how that makes left one non empty

[zenu]

what if
A
/
A
/
A
?
there will be no use to dismiss the
middle A.