0
$\begingroup$

$$ L=\{a^ib^jc^k \;| \;i, j, k \in \mathbb{N} \; \text{and} \; i <k<j\} $$

I need to show that this language is not context-free with the help of the Pumping Lemma. My first intuition is, that there exist 5 different cases, i.e. the middle part, let's call it vwx, consists of

  1. only $a$'s
  2. only $b$'s
  3. only $c$'s
  4. $a$'s and $b$'s
  5. $b$'s and $c$'s

and I need to find a pumping constant, which excludes the new word from the above defined language. However, I am having a hard time how show that formally and precisely. Any hints are highly appreciated!

$\endgroup$
1
1
$\begingroup$

Your case analysis seems right and can be used to prove non-contextfreeness.

Not you don't have to find a pumping constant. To the contrary, you have to show no such constant can exist. So, the general argument is usually like "if I assume $N$ is the pumping constant, I can use this word $x\in L$, longer than $N$, and whatever I try, we cannot pump it and stay in $L$."

Usually one choses a string that is "just" inside the language, in this case $a^Nb^{N+1}c^{N+2}$. Now check your cases. What if we pump $a$'s and or $b$'s, but no $c$'s etcetera.

One final hint, which seems necessary here. One cannot only "pump up", but also "pump down".

$\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.