I understand what Pumping Lemma is, how it works and also understand it's proof. The gist is that it uses "Pigeon Hole" principle to guarentee us a repeatation in the sequence of states and we use that repeatation as an exploit to prove non regularity using contradiction

There is a condition $|xy| <= p$, this condition guarentees us that we focus on first repeatation, which makes sense.

Now, we know that to use pumping lemma we need to "prove that a language is non regular" we need to assume that the language is regular and pick a specific word ~ 'w' from the language, and decompose that 'w' into w = xyz

My question is that since we need to pump only one certain loop, the very first loop, can x can a loop? or does it need to have only those symbols that take the finite automata through a distinct set of states? similarly for z

In the following, by distinct I mean ~ the mentioned part does not have any loops

This first link which proves pumping lemma say's 'x' part of decomposition must be distinct: https://cs.stackexchange.com/a/133970/150275

Whilst in this example the user didn't take the 'x' part of decomposition as distinct: Pumping Lemma: 1^n^2 is not regular and even in this one https://math.stackexchange.com/questions/1209631/proving-0n-1n-2n-n-0-is-not-regular

They didn't allow the x part to be distinct, now here is the thing, if they don't take the x part as distinct ~ and choose other loop part in y, then they aren't considering the very first loop guareented by pumping lemma, they are using some other loop

Tldr: Should the x part of the decomposition be distinct or not?



Your Answer

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

Browse other questions tagged or ask your own question.