0
$\begingroup$

$\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language.

I attempted to try this, but I keep on getting stuck. I was planning on solving it like a pumping lemma question for grammar, but I am not sure.

Thank you!

$\endgroup$
0
$\begingroup$

The pumping lemma gives a necessary condition for a language to be a CFL, so a common way to show that a language is not a CFL is to show that the pumping lemma's condition is not satisfied. However, the language given $\textbf{does}$ satisfy the required condition, so the pumping lemma tells us nothing about the language.

Let $L=\{a^ib^jc^k | i>j>k>0\}$ and let the pumping length $p=1$ (there are no strings in $L$ of length less then $6$ except the empty string, so this is really the same thing as $p=6$). For a string $s=uvwxy$, let $v=a$ and let $w,x$ be the empty strings. Each string in $L$ starts with an $a$, so we can write $s=uvwxy$ where $u,w,x$ are the empty string, $v$ is $a$ and $y$ is the rest of the string. This satisfies the conditions of the pumping lemma:

  • $|vwx|=|a|=1\le 1=p \implies |vwx|\le p$
  • $|vx|=|a|=1 \implies |vx|\ge 1$
  • $uv^nwx^ny=v^ny=a^ny=a^{n-1}s\in L\implies uv^nwx^ny\in L$ for all $n\ge 0$

Therefore, it is not possible to show that $L$ is not a CFL using the pumping lemma.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.