Ana səhifə

Examples of the use of the pumping lemma for cfl's Example 1: Let L = {0


Yüklə 20.03 Kb.
tarix24.06.2016
ölçüsü20.03 Kb.
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.


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©atelim.com 2016
rəhbərliyinə müraciət