Re: Pumping lemma. Where I go wrong?

Ravi <ra.ravi.rav@xxxxxxxxx> wrote:
In your example, it might happen that x = 00, y = 0^{2n - 2}, so
you wouldn't get the contradiction you need in (4) below.

Thanks Mr. Rick. But wont we need to take all the situations.

No. There is a difference between quantifiers "there exists..." and
"for all...". The pumping lemma is stated like this,

FOR ALL regular languages
THERE EXISTS a pumping length n such that
FOR ALL strings in the language
THERE EXISTS a partition into x, y, and z
such that some conditions are true.

The lemma doesn't guarantee that the conditions hold for all possible
values of n, x, y, and z; but only that there is SOME pumping length,
and that there is SOME x, y, and z so that it is true. If you want to
disprove that (and therefore show that the language is non-regular), you
have to show that there is no set of values for n, x, y, and z for which
it's true. You don't get a contradiction by showing that there are
values where it's not true.

This is different from the "FOR ALL" parts. In those cases, the lemma
asserts that its conclusion will be true regardless of what regular
language or string is considered, so you get to make your own choices
and finding even one counterexample is sufficient to obtain the
contradiction.

So the exact wording of the lemma matters quite a lot when you're trying
to contradict it.

--
Chris Smith
.

Relevant Pages

  • Re: Neural netss (was Re: death of the mind.)
    ... > is point out the errors and consequences of various doctrines. ... want to talk with those people, you must learn their language - if you ... > doctrines and possibly incremental modifications within that context. ... Yes logical contradiction - basically the law of the excluded middle ...
    (sci.cognitive)
  • Re: infinity
    ... then lets look at the language of strings on ... There are an infinite number of finite k. ... The contradiction is not in the idea of a finite set but in naming the size F ...
    (sci.math)
  • Re: infinity
    ... >>> srings in the language. ... then lets look at the language of strings on ... There are an infinite number of finite k. ... Do you really not see the contradiction? ...
    (sci.math)
  • Re: infinity
    ... then lets look at the language of strings on ... So when I plug in all the finite L, I get an infinite ... of finite numbers that it leads to a contradiction. ...
    (sci.math)
  • Re: Godels comments about the "true reason" for incompleteness
    ... arbitrary Q. Obviously there is an implied quantification over Q, ... letters of the object language). ... we want to convey that "all" propositions follow from a contradiction. ... refutable in PA and as confirmed by the supposed undecidability of S. ...
    (sci.logic)