worksheet8.org

In-Class Worksheet 8: Context-Free Pumping Lemma

Try to prove, using the context-free pumping lemma, that the following languages are not context-free.

• { ww^Rw | w ∈ {0,1}^* }
• {m+n=p | where m,n,p are binary strings and m + n = p as numbers}
• { 0^{2^n} | n ≥ 0} (this one is a bit tricky)