0
$\begingroup$

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?

$\endgroup$

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.