Appendix E. Pumpable Cfl

Appendix E. A CFL Satisfying the Pumping Lemma for Regular Languages We showed that every infinite regular language satisfies the pumping lemma. We proved this lemma with no regard to other classes of languages. As an application of the lemma we showed that context-free language {aibi | i > 0 } does not satisfy the lemma and hence, is not regular. We may ask the following. Is every non-regular context-free language does not satisfy the lemma? Or otherwise, is there a non-regular language which satisfies the pumping lemma? Here we show a non-regular context-free language that satisfies the pumping lemma, giving positive answer for the later question. (This example is given by one of the author’s colleagues Professor Robert McNaughton at RPI.) L1 = {x | x ∈ {a, b}*, x has aa or bb as a substring.} L2 = {x | x ∈ {a, b}*, |x| = p, p is a prime number } L1 = {a, b}* - L1

// complement of L1

L = ( L1 ∩ L2 ) ∪ L1 // L is a non-regular language satisfying the lemma. 1

Proof

CFL Satisfying the Pumping Lemma

We will prove why L satisfies the lemma. L1 is regular. We can prove this by the fact that L1 can be expressed by a regular expression or the complement of L1 can be recognized by an NFA shown below, because regular languages are closed under complementation. a,b a,b a a (ab)* + b(ab)* + (ab)*a + (ba)* b b a,b L1 = {x | x ∈ {a, b}*, x has no aa or bb as a substring.} L2 = {x | x ∈ {a, b}*, |x| = p, p is a prime number } L1 = {a, b}* - L1

// complement of L1

L = ( L1 ∩ L2 ) ∪ L1 // L is a non-regular language satisfying the lemma.

2

Proof

CFL Satisfying the Pumping Lemma

We will first show that L is not regular. Suppose L is regular. According to the properties of regular languages, since L1 is regular, L - L1 = L1 ∩ L2 must also be regular. Since this language is infinite, it should satisfy the pumping lemma. Let n be the constant of the pumping lemma, and choose a string z in L1 ∩ L2 whose length is greater than n. Let z = uvw such that |uv| ≤ n and |v| ≥ 1. Now, we pump z and make z’ = uvpj+1 w, where j = |v| and p = |z| is a prime number according to the condition of L2 . Clearly, the length of z’ is |z’| = p + |v|× pj = p(1 + j2 ), which is not a prime number. It follows that z’ ∉ L1 ∩ L2 . The language L1 ∩ L2 is not regular, implying that L is not regular. L1 = {x | x ∈ {a, b}*, x has no aa or bb as a substring.} L2 = {x | x ∈ {a, b}*, |x| = p, p is a prime number } L1 = {a, b}* - L1

// complement of L1

L = ( L1 ∩ L2 ) ∪ L1 // L is a non-regular language satisfying the lemma.

3

Proof

CFL Satisfying the Pumping Lemma

L1 = {x | x ∈ {a, b}*, x has no aa or bb as a substring.} L2 = {x | x ∈ {a, b}*, |x| = p, p is a prime number } L1 = {a, b}* - L1

// complement of L1

L = ( L1 ∩ L2 ) ∪ L1 // L is a non-regular language satisfying the lemma. Now, we will prove that language L satisfies the pumping lemma. For the proof, we must show that there exists a constant n such that for every string z ∈ L whose length is greater than or equal to n, there exists strings u, v and w that satisfy the following conditions. (i) z = uvw

(ii) |uv| ≤ n (iii) |v| ≥ 1

(iv) For all i ≥ 0, uviw ∈ L Let z = c1c2c3x be a string in L, where ci ∈ {a, b}, x ∈ {a, b}*, |x| ≥ n - 3.

4

Proof

CFL Satisfying the Pumping Lemma

L1 = {x | x ∈ {a, b}*, x has no aa or bb as a substring.} L2 = {x | x ∈ {a, b}*, |x| = p, p is a prime number } L1 = {a, b}* - L1

// complement of L1

L = ( L1 ∩ L2 ) ∪ L1 // L is a non-regular language satisfying the lemma. Let n = 3, and consider the following 3 cases. Case 1: c1 ≠ c2 ≠ c3 (i.e., z = abax, or z = babx). Let u = c1, v = c2 and w = c3x. Then, clearly, for every i ≥ 0, z' = uviw ∈ L. ( Specifically, if i = 1, then z' ∈ L. Otherwise, z' ∈ L1.) Case 2: c1 = c2 (i.e., z ∈ L1). Let u = c1c2, v = c3 and w = x. Then for all i ≥ 0, we have z' = uviw ∈ L (specifically, z' ∈ L1). Case 3: c2 = c3 (z ∈ L1 ). Let u = ε , v = c1 and w = x. Then again, for all i ≥ 0, we have z' = uviw ∈ L. It follows that language L satisfies the pumping lemma. 5