pumping-lemma

Unable to prove this language is not context-free using Pumping Lemma

I'm trying to prove that the language { w ϵ {a, b, c}* | n_a(w) < n_b(w) and n_a(w) < n_c(w) } is not a CFL using Pumping Lemma. The symbol "n_a" represents "number of 'a'".

For pumping lemma, z = u(v^i)x(w^i)y, |vxw| <= m, |vw| >= 1.

I've chosen to use the string z = (a^m)b^(m+1)c^(m+1) to show this isn't a CFL.

However, I get stuck on the following case.

Assume 'uvx' represents the (a^m) portion of 'z', 'w' represents the beginning of the (b^m) portion of 'z' and 'y' represents the rest of 'z'.

Now pumping for i = 2, we get z' = u(v^2)x(w^2)y = a^(m + |v|)b^(m + 1 + |w|)c^(m + 1).

Whenever |v| ≠ 0, we see that this isn't in the language, since n_a(z') is not less than n_c(z'). However, for the case where |v| = 0, we get z' = a^(m)b^(m + 1 + |w|)c^(m + 1), which IS in the language. Therefore, pumping with i = 2 would not work. Is this correct?

I tried with other values of 'i', but I'm still not able to prove this language is not a CFL. What am I doing wrong? Is this language actually context-free? Should I be using a completely different 'z' string?

Solution

  • Let R be a non-terminal that indicates the following:

    There are no more a than there are b or c in the final product

    Stated alternatively:

    For w ϵ G(R), n_a(w) <= n_b(b) and n_a(w) <= n_c(w)

    So the rules for this guy are (let ϵ be the empty string):

    R => ϵ

R => bR
R => Rb
R => cR
R => Rc

R => abcR
R => abRc
R => aRbc
R => Rabc

R => acbR
R => acRb
R => aRcb
R => Racb

R => bacR
R => baRc
R => bRac
R => Rbac

R => bcaR
R => bcRa
R => bRca
R => Rbca

R => cbaR
R => cbRa
R => cRba
R => Rcba

R => cabR
R => caRb
R => cRab
R => Rcab

    Those 29 are all the possibles transformations that guarantees that any word derived from R will have no more as than bs and no more as than cs.

    But the question isn't about G(R), it is stated explicitly that n_a(w) <= n_b(b) and n_a(w) <= n_c(w). So, I'll have 3 more non-terminals:

    1. S, the start point
    2. B, derived directly or indirectly from S and guaranteed to have at least one more b than a (considering how it"isborn")
    3. C, derived directly or indirectly from S and guaranteed to have at least one more c than a (considering how it"isborn")

    My strategy will be the following:

    Those non-terminals will all be similar to R, but they won't have any empty transformation; also, from S I'll have a transformation that will generate bB, or Bb, or cC, or Cc; from B, it is guaranteed to have at least one b more than a, then it will have a transformation to cR or Rc; and for C, transformation to bR or Rb

    So, this will be my complete grammar, starting with S:

    S => bB
S => Bb
S => cC
S => Cc

S => bS
S => Sb
S => cS
S => Sc

S => abcS
S => abSc
S => aSbc
S => Sabc

S => acbS
S => acSb
S => aScb
S => Sacb

S => bacS
S => baSc
S => bSac
S => Sbac

S => bcaS
S => bcSa
S => bSca
S => Sbca

S => cbaS
S => cbSa
S => cSba
S => Scba

S => cabS
S => caSb
S => cSab
S => Scab

B => cS
B => Sc

B => bB
B => Bb
B => cB
B => Bc

B => abcB
B => abBc
B => aBbc
B => Babc

B => acbB
B => acBb
B => aBcb
B => Bacb

B => bacB
B => baBc
B => bBac
B => Bbac

B => bcaB
B => bcBa
B => bBca
B => Bbca

B => cbaB
B => cbBa
B => cBba
B => Bcba

B => cabB
B => caBb
B => cBab
B => Bcab

C => bR
C => Rb

C => bC
C => Cb
C => cC
C => Cc

C => abcC
C => abCc
C => aCbc
C => Cabc

C => acbC
C => acCb
C => aCcb
C => Cacb

C => bacC
C => baCc
C => bCac
C => Cbac

C => bcaC
C => bcCa
C => bCca
C => Cbca

C => cbaC
C => cbCa
C => cCba
C => Ccba

C => cabC
C => caCb
C => cCab
C => Ccab


R => ϵ

R => bR
R => Rb
R => cR
R => Rc

R => abcR
R => abRc
R => aRbc
R => Rabc

R => acbR
R => acRb
R => aRcb
R => Racb

R => bacR
R => baRc
R => bRac
R => Rbac

R => bcaR
R => bcRa
R => bRca
R => Rbca

R => cbaR
R => cbRa
R => cRba
R => Rcba

R => cabR
R => caRb
R => cRab
R => Rcab