Pumping Lemma for Context-Free Languages: Four Examples
Easy Theory Easy Theory
25.8K subscribers
50,672 views
0

 Published On Premiered Nov 16, 2020

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:    / @easytheory  

▶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.

show more

Share/Embed