1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Nov 20, 2014 at 17:39

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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