Question

Use the pumping lemma for context-free languages to prove that L₃ is not a CFL.

L3 = { w: w e{a,b,c}* and na(w) < nh(w) < nc(w) }.

Answer 1

Let us assume that the string z = aⁿbⁿ⁺¹cⁿ⁺² belongs to L.

Let us assume that L is context-free.

Now, let us assume that u = a^p, v = a^n-p, w = b^q, x = b^n+1-q, y = cⁿ⁺²

Now, in order for L to be CFL, the string uvⁱwxⁱy should belong to L too.

uvⁱwxⁱy = a^{(2ni - pi + p)} b^{(2ni - qi + q + 1)} c^{(n + 2)}

Clearly, for larger values of i, we cannot guarantee that

(2ni - pi + p) < (n+2) or (2ni - qi + q + 1) <= (n + 2).

Hence, L is not CFL.