-2
$\begingroup$

How can I negate the following sentence: For all words x from L with |x|>= n , exists decomposition x = uvw with |uv| <= n and |v| >= 1, so for all i >= 0 , is valid that u(v)^iw in L is.

$\endgroup$
  • 1
    $\begingroup$ Did you try en.wikipedia.org/wiki/De_Morgan's_laws ? What did you get? $\endgroup$ – chi May 19 '17 at 19:10
  • $\begingroup$ For at least one word x from L with |x|>= n , exists decomposition x = uvw with |uv| <= n and |v| >= 1,so for at least one i >= 0 , is valid that u(v)^iw not in L is. Is this the right way ? $\endgroup$ – unnamed May 19 '17 at 19:15
  • $\begingroup$ The part "For at least one word x from L with |x|>= n , " is correct. But "exists decomposition such that ..." must be negated, so it becomes "for all decompositions, we do not have ..." (and then we push the negation further). $\endgroup$ – chi May 19 '17 at 19:27
  • $\begingroup$ Is this actually the negation of the pumping lemma ? $\endgroup$ – unnamed May 19 '17 at 19:34
  • $\begingroup$ Write it as formula. Slap $\lnot$ in front. Done. $\endgroup$ – Raphael May 20 '17 at 5:15
0
$\begingroup$

The negation is: There exists a word $x \in L$ satisfying $|x| \geq n$ such that for all decompositions $x = uvw$ with $|uv| \leq n$ and $|v| \geq 1$ there exists $i \geq 0$ such that $uv^iw \notin L$.

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