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

Question

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?

Are you sure this isn't CFL? Maybe there is a grammar that states that maybe it is indeed context-free? If I find one such, I'll post as an answer — Jefferson Quesado
I think I found one with about 50 transformation rules! One minute while I write it down — Jefferson Quesado
@JeffersonQuesado This question is from an assignment which asks to 'use the Pumping Lemma for CFL's to show that the following language is not Context-Free.' I would assume it's not CF because of the way the question is phrased, but the professor has made mistakes in the assignment questions in the past. I tried building a PDA for the language, but it got a little complex, which further led me to believe it's not CF. Thank you, please let me know if you find something! — Ioannis Georgantas
I'm voting to close this question as off-topic because it is not a programming question. — Raymond Chen
So, 121 transformations for the goal? May it is a little bit repetitive, maybe one can simplify all those rules, but I think I got it right — Jefferson Quesado

Jefferson Quesado Jefferson Quesado · Accepted Answer · 2017-04-01T02:58:01

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:

S, the start point
B, derived directly or indirectly from S and guaranteed to have at least one more b than a (considering how it"isborn")
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

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

1 Answers