For proving language $\{a^nb^mc^nd^m \mid n,m > 0\}$ is not context free. Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length?

Or do I have to use a string that would reflect than $n$ and $m$ does not have to be the same length?

  • $\begingroup$ Note our reference question which describes the Pumping lemma and other methods in detail. Hint: If you read $a$ and $b$ as $($, and $c$ and $d$ as $)$, you have crossing balanced parentheses. That's general a no-go pattern of CFL. $\endgroup$ – Raphael Nov 20 '14 at 17:39

Pumping lemma lets you construct new strings belonging to the context-free language.

To prove that the language is not context-free you can take some string $s$ from L, use pumping lemma to construct a new string $s1$ which must belong to $L$ (because you used pumping lemma to construct it!). Then you show that $s1$ does not belong to L => contradiction.

Choice of original $s$ is yours. So yes, you can use $z = a^pb^pc^pd^p$ in your proof.

| cite | improve this answer | |

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.