You've made some very fundamental mistakes. Pumping Lemma is used as an _adversarial_ argument. This has the following implications, 1) _You_ as the one who is trying to prove that a language is NOT regular will not be choosing `n'. The adversary chooses `n'. 2) Once the adversary has chosen `n', you choose a string longer than n, in order to ensure there is a loop (the pumping property). 3) The adversary then chooses the split up, that is, the part of the string you've given him that loop. The way you've defined it, xyz, subject to the constraint that |xy| <= n. 4) You pump as many times as you wish to disprove his statement.
On 4/6/07, Ravi <[EMAIL PROTECTED]> wrote: > > 3)Choose x = 0, y = 0^n-1, z = 1^2b So this is where you go wrong. A _smart_ adversary will not choose x and y the way you have. He could quite easily have choosen x=0^n-2, y=0^2, z=the rest. The basic flaw is that you've ignored the fact that the pumping lemma is used as an adversarial dialogue, between, you, the person trying to prove a language is not regular, and someone, who claims to have a finite state machine that accepts that language. -- Regards, Rajiv Mathews --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
