CF Pumping Lemma, Turing Machines

• Proving languages not Context Free
• Turing machine

$\setminus \setminus$

Pumping Lemma for CFGs

For every CFL A, there is a p such hat if $s\in A$ and $|s|\ge p$ then $s=uvxyz$ where

1. $u{v}^{i}x{y}^{i}z\in A$ for all $i\ge 0$
2. $vy\ne ϵ$
3. $|vxy|\le p$

Informally: All long strings in $A$ are pumpable and stay $A$