Examples of the use of the pumping lemma for CFL's
Example 1: Let L = {0^{i}1^{i}2^{i} | i 0}
Assume L is a CFL and let m be the integer of the pumping lemma. Let w = 0^{m}1^{m}2^{m}. Clearly, w L so w can be decomposed as w = uvxyz such that |vxy| m, |vy| 1, and uv^{i}xy^{i}z is in L for every i 0. To arrive at a contradiction, consider the following cases.
Case 1: v and/or y contains two different symbols. First, note that neither v nor y can contain both 0's and 2's because of the restriction on the length of vxy.
a. v contains both 0's and 1's. Then y contains only 1's. If i = 0, w_{0} = uv^{i}xy^{i}z = uxz = 0^{k}1^{j}2^{m}^{ }and, since k, j < n, the resulting string is not in L.
b. y contains both 1's and 2's. Then v contains only 1's. If i = 0, w_{0} =uv^{i}xy^{i}xz = uxz = 0^{m}1^{k}2^{j}^{ }and, since k, j < m, the resulting string is not in L.
Case 2: v and y each contain only one alphabet symbol. Without loss of generality assume that y . The cases where v is not the empty string are analogous. In all cases, the string that results from letting i = 0 is not in L.
a. v 0*, y 0^{+}. Then, let i = 0 so that w_{0} = uxz = 0^{k}1^{m}2^{m}^{ }^{with k < m.}
b. v 0*, y 1^{+}. Then, let i = 0 so that w_{0} = uxz = 0^{k}1^{j}2^{m}^{ }^{with j < m.}
^{ c. v }^{}^{}^{1*, y }^{}^{ }1^{+}. Then, let i = 0 so that w_{0} = uxz = 0^{m}1^{k}2^{m}^{ }^{with k < m.}
d. v 1*, y 2^{+}. Then, let i = 0 so that w_{0} = uxz = 0^{m}1^{k}2^{j}^{ }^{with j < m.}
e. v 2*, y 2^{+}. Then, let i = 0 so that w_{0} = uxz = 0^{m}1^{m}2^{k}^{ }^{with k < m.}
^{Since we have shown that no matter how w is broken up into uvxyz, there is a value of i such that }uv^{i}xy^{i}z is not in L, the initial assumption that L was context-free is false.
Example 2: L = {a^{n}b^{j}c^{k} | k >n, k > j}
Assume L is a CFL and let m be the pumping lemma integer. Choose w = a^{m}b^{m}c^{m+1}. Clearly, w L. Then w can be decomposed as w = uvxyz such that |vxy| m, |vy| 1, and uv^{i}xy^{i}z is in L for every i 0. To arrive at a contradiction, consider the following cases.
Case 1: v and y contain the same symbol
a. both contain a. Let i = 2. Then w_{2} = uv^{2}xy^{2}z has the form a^{m+j}b^{m}c^{m+1}. Since j ≥ 1, w_{2} L
b. both contain b. Let i = 2. Then w_{2} = uv^{2}xy^{2}z has the form a^{m}b^{m+j}c^{m+1}. Since j ≥ 1, w_{2} L
c. both contain c. Let i = 0. Then w_{0} = uxz has the form a^{m}b^{m}c^{m+1-j}. Since j ≥ 1, w_{0} L
Case 2: v and y contain different symbols and without loss of generality assume y ≠
a. v a*, y b^{+}. Let |y| = j and let i = 2. w_{2} = a^{m}b^{m+j}c^{m+1}. Since j ≥ 1, w_{2} L
b. v b*, y c^{+}. Let |y| = j and let i = 0 w_{0} = uxz = a^{m}b^{m}c^{m+1-j}. Since j ≥ 1, w_{0} L
Case 3: v or y contains two different symbols
a. v contains both a's and b's. Then y contains only b's. If i = 2, uv^{2}xy^{2}z = a^{m}b^{j}a^{i}b^{m}c^{m+1}^{ }and, since i, j > 1, m+1 ≤ m+j so w_{2} L.
b. y contains both b's and c's. Then v contains only b's. If i = 0, uxz = a^{m}b^{m+j}c^{m+1-k}^{ } and since k ≥ 1, m+1-k ≤ m and the string is not in L.
^{Since we have shown that no matter how w is broken up into uvxyz, there is a value of i such that }uv^{i}xy^{i}z is not in L, the initial assumption that L was context-free is false. |