received_936490232006650.jpeg

# Lecture 24: Pumping Lemma ## Non-Context-Free Languages **Example:** $\{a^n b^n c^n \mid n \geq 0\}$ is not context-free. **Proof:** 1. Assume $L = \{a^n b^n c^n \mid n \geq 0\}$ is context-free. 2. Let $p$ be the pumping length. 3. Let $s = a^p b^p c^p$. Clearly, $|s| = 3p \geq p$. 4. By...

# Lecture 24: Pumping Lemma ## Non-Context-Free Languages **Example:** $\{a^n b^n c^n \mid n \geq 0\}$ is not context-free. **Proof:** 1. Assume $L = \{a^n b^n c^n \mid n \geq 0\}$ is context-free. 2. Let $p$ be the pumping length. 3. Let $s = a^p b^p c^p$. Clearly, $|s| = 3p \geq p$. 4. By the pumping lemma, $s = uvxyz$, where $|vxy| \leq p$ and $vx \neq \epsilon$, such that for all $i \geq 0$, $uv^i xy^i z \in L$. * Case 1: $vxy$ contains only one type of symbol. * If $vxy$ contains only $a$'s, then $uv^2 xy^2 z$ will have more $a$'s than $b$'s and $c$'s. * Similarly, if $vxy$ contains only $b$'s or only $c$'s, $uv^2 xy^2 z \notin L$. * Case 2: $vxy$ contains two types of symbols. * $vxy$ cannot contain all three types of symbols because $|vxy| \leq p$. * If $vxy$ contains $a$'s and $b$'s, then $uv^2 xy^2 z$ will have the form $a^+ a^+ b^+ b^+ c^+$, where the $a$'s and $b$'s are out of order. * Similarly, if $vxy$ contains $b$'s and $c$'s, then $uv^2 xy^2 z \notin L$. 5. Since in all cases $uv^2 xy^2 z \notin L$, the pumping lemma condition is violated. Thus, our initial assumption is wrong. 6. Therefore, $L = \{a^n b^n c^n \mid n \geq 0\}$ is not context-free. **Example:** $L = \{ww \mid w \in \{0, 1\}^*\}$ is not context-free. **Proof:** 1. Assume $L = \{ww \mid w \in \{0, 1\}^*\}$ is context-free. 2. Let $p$ be the pumping length. 3. Let $s = 0^p 1^p 0^p 1^p$. Clearly, $|s| = 4p \geq p$. 4. By the pumping lemma, $s = uvxyz$, where $|vxy| \leq p$ and $vx \neq \epsilon$, such that for all $i \geq 0$, $uv^i xy^i z \in L$. * Case 1: $vxy$ occurs in the first $0^p$. Then $uv^2 xy^2 z$ is no longer of the form $ww$ since the first $w$ is longer than the second $w$. * Case 2: $vxy$ occurs in the first $1^p$. Then $uv^2 xy^2 z$ is no longer of the form $ww$ since the first $w$ is longer than the second $w$. * Case 3: $vxy$ spans the first $1^p 0^p$. Since $vx \neq \epsilon$, either the number of 1's or 0's in the first $w$ changes, but the number of 1's and 0's in the second $w$ does not change. Thus, $uv^2 xy^2 z$ is no longer of the form $ww$. 5. Since in all cases $uv^2 xy^2 z \notin L$, the pumping lemma condition is violated. Thus, our initial assumption is wrong. 6. Therefore, $L = \{ww \mid w \in \{0, 1\}^*\}$ is not context-free.