Pumping Lemma for Context-Free Languages: Four Examples

Here we give four proofs of languages not being context-free: 1) {a^n b^n c^n : n at least 0} 2) {a^i b^j c^k : i at most j, j at most k} 3) {ww : w in {0,1}*} 4) {w in {a,b,c,d}* : w has more c's than a's, b's, or d's} In each, we go through a proof to show that each language is not context-free by first assuming that it is context-free, then using the fact that there is a pumping constant p for each language, finding a string that cannot be pumped. Timestamps: 0:00 - Intro 1:00 - Main steps in proofs 3:30 - {a^n b^n c^n : n at least 0} 14:20 - {a^i b^j c^k : i at most j, j at most k} 24:00 - {ww : w in {0,1}*} 37:30 - {w in {a,b,c,d}* : w has more c's than a's, b's, or d's} If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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.