Using the Pumping Lemma to Prove $L = \{a^ib^jc^k \mid i < j < k\}$ is not Context-Free

6.4k Views Asked by At

I want to use the Pumping Lemma to prove that $$L = \{a^ib^jc^k \mid i < j < k\}$$ is not context-free. I think I have the intuition, but I don't know how to prove it. Help?

1

There are 1 best solutions below

3
On BEST ANSWER

For arbitrary $j>1$ take the word $ab^jc^{j+1}$. Since $ab^jc^{j+1}=a\cdot b\cdot b^{j-1}\cdot c^{j+1}$ then for all $m$ we have $a\cdot b^m\cdot b^{m(j-1)}\cdot c^{j+1}\in L$. But it is impossible for $m\ge 2$.