18.404J F2020 Lecture 5: CF Pumping Lemma, Turing Machines

Let ! = 0 $ 1 $ 2 $ ' ≥ 0}. We will show that ! isn’t a CFL. Pumping Lemma for CFLs: For every CFL *, there is a + such that if , ∈ * and , ≥ + then , = ./012 where . 1) ./ 3 01 3 2 ∈ * for all 4 ≥ 0 2) /1 ≠ ε 3) /01 ≤ +, = ≥ +. / 0 1 2 ∈ * Informally: All long strings in * are pumpable and stay in *. ∈ *. / / 1 2. ≤ ... ................
................

In order to avoid copyright disputes, this page is only a partial summary.