Prove that $L=\{a^kb^mc^{m-k}|m\ge k\ge0, m-k\ge k\}$ is not context-free language.

We can suppose by contradiction that $L$ is context-free and choose $Z=a^kb^{2k}c^k$.

Using pumping lemma, $vwx$ can't have both $a$'s and $c$'s because $|vwx|\le k$. There're $3$ cases:

1) $a\notin vx, |vx|\ge 1$ and $b\in vx$. For $i=0:$ $$ Z_0=uv^0wx^0y=a^kb^{2k-l}c^{k-t}\\l\ge 1\\t\ge 0 $$ In this case $2k-l\le 2k\implies Z_0\notin L$.

2) $a\notin vx, |vx|\ge 1$ and $b\notin vx$ and $c\in vx, |vx|\ge 1$. For $i=0:$ $$ i=0: Z_0= uv^0wx^0y=a^kb^{2k-t}c^{k-l}\\l\ge 1\\t\ge 0 $$ In this case $k-l<k\implies Z_0\notin L$

3) $a\in vx, |vwx|\le k, c\notin vx$. For $i=0:$ $$ Z_0=uv^0wx^0y=a^{k-l}2^{2k-t}c^k $$ In this case $k-l<k\implies Z_0\notin L$

I'm not sure that my proof good. If not what are my mistakes?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.