Formal Language - Ch8 上下文無關語言泵引理 Pumping lemma for context free languages

1. $\left| vxy \right| \le n$
2. $\left| vy \right| > 0$
3. $\forall k \ge 0:uv^kxy^kz \in L$

[用心去感覺] 哪些語言是上下文無關?

[例題] 三組符號 - Showing that $\{a^nb^nc^n: n ≥ 0\}$ is not a CFL
• 假設$a^Nb^Nc^N$屬於$L$語言的字串且比$N$長
($N$就是狀態個數，一個機器給$N$個狀態，要想辦法找到字串比$N$更長來達到重複的鴿籠效果)
• 所以可以把$w$寫成$w = uvxyz$的形式($\left| vxy \right| \le n$, $\left| vy \right| > 0$)
• 而我們能證明存在$i$使$uv^ixy^iz$不在語言L中

1. $vy$包含全部符號$a,b,c$，那麼$uv^ixy^iz$時$a,b,c$的順序會錯，例如 $(aa)(aaabb)(bb)(bccc)(cc)$變成$(aa)(aaabb)(aaabb)(bb)(bccc)(bccc)(cc)$，因此不在L中。
2. $vy$不包含全部符號時，$uv^ixy^iz$會有不相同數量的a,b,c，例如$(aa)(aaa)(bbbbb)(ccc)(cc)$變成$(aa)(aaa)(aaa)(bbbbb)(ccc)(ccc)(cc)$，因此不在L中。

[例題] 重複ww - Showing that $E = \{ww\ |\ w \in \{0,1\}^*\}$ is not a CFL

Proof. Suppose E is context-free. Let p be the pumping length.

• Consider $z = 0^p1^p0^p1^p \in L$.
• Since $|z| > p$, there are $u, v, w, x, y$ such that $z = uvwxy, |vwx| ≤ p, |vx| > 0$ and $uv^iwx^iy \in L$ for all $i ≥ 0$.
• $vwx$ must straddle the midpoint of $z$.
• – Suppose $vwx$ is only in the first half. Then in $uv^2wx^2y$ the second half starts with 1. Thus, it is not of the form $ww$.
• – Case when $vwx$ is only in the second half. Then in $uv^2wx^2y$ the first half ends in a 0. Thus, it is not of the form $ww$.
• – Suppose $vwx$ straddles the middle. Then $uv^0wx^0y$ must be of the form $0^p1^i0^j1^p$, where either $i$ or $j$ is not $p$. Thus, $uv^0wx^0y \notin E$.

[例題]  Same number of 0s and 1s
1.   Showing that L = {w | w has the same number of 0s and 1s} is a CFL
Grammar G :
A → 0A1A | 1A0A
A → ε

2.   Showing that B = {w|w is a palindrome over {0, 1} and w contains an equal number of 0s and 1s}

Reference

wiki - Pumping lemma for context-free languages
http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages