Examples of the use of the pumping lemma for CFL's
Example 1: Let L = {0i1i2i | i 0}
Assume L is a CFL and let m be the integer of the pumping lemma. Let w = 0m1m2m. Clearly, w L so w can be decomposed as w = uvxyz such that |vxy| m, |vy| 1, and uvixyiz 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, w0 = uvixyiz = uxz = 0k1j2m 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, w0 =uvixyixz = uxz = 0m1k2j 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 w0 = uxz = 0k1m2m with k < m.
b. v 0*, y 1+. Then, let i = 0 so that w0 = uxz = 0k1j2m with j < m.
c. v 1*, y 1+. Then, let i = 0 so that w0 = uxz = 0m1k2m with k < m.
d. v 1*, y 2+. Then, let i = 0 so that w0 = uxz = 0m1k2j with j < m.
e. v 2*, y 2+. Then, let i = 0 so that w0 = uxz = 0m1m2k 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 uvixyiz is not in L, the initial assumption that L was context-free is false.
Example 2: L = {anbjck | k >n, k > j}
Assume L is a CFL and let m be the pumping lemma integer. Choose w = ambmcm+1. Clearly, w L. Then w can be decomposed as w = uvxyz such that |vxy| m, |vy| 1, and uvixyiz 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 w2 = uv2xy2z has the form am+jbmcm+1. Since j ≥ 1, w2 L
b. both contain b. Let i = 2. Then w2 = uv2xy2z has the form ambm+jcm+1. Since j ≥ 1, w2 L
c. both contain c. Let i = 0. Then w0 = uxz has the form ambmcm+1-j. Since j ≥ 1, w0 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. w2 = ambm+jcm+1. Since j ≥ 1, w2 L
b. v b*, y c+. Let |y| = j and let i = 0 w0 = uxz = ambmcm+1-j. Since j ≥ 1, w0 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, uv2xy2z = ambjaibmcm+1 and, since i, j > 1, m+1 ≤ m+j so w2 L.
b. y contains both b's and c's. Then v contains only b's. If i = 0, uxz = ambm+jcm+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 uvixyiz is not in L, the initial assumption that L was context-free is false. |