Consider this snippet shown below from, An Introduction to Formal Languages and Automata 6th Edition by Peter Linz.

enter image description here

As per the text, choosing a value of $y = a^k$, where $k$ is odd is not permitted since this violates the condition of pumping lemma. This text simply says that the assumption on $k$ (number of $a$'s in $y$ being odd) is not permitted.

Now, as far as my understanding goes, the condition on choosing $xy$ is $|xy| \le p$, where $p$ is the pumping length, and $|y|>1$. And if we can show that one valid choice of $y$ satisfies the pumping lemma, we have been able to show that this language does not violate the pumping lemma, though the language can not be claimed to be regular. When I need to show that the language is not regular, I need to explore all possible $y$'s.

I fail to understand, why a $y$, with odd number of $a$'s, and $|y| \le p$, $x=\epsilon$, will not be permitted here.

  • $\begingroup$ If you are using the pumping lemma to prove $L$ is not regular then you are not permitted to make the assumption that $y$ has odd length, or any other assumption of this kind. It is not clear what you want to achieve. $\endgroup$ – Michal Adamaszek Dec 5 '18 at 9:05
  • $\begingroup$ @MichalAdamaszek Would you mind elaborating, "any other assumption of this kind", part? $\endgroup$ – Masroor Dec 5 '18 at 9:15
  • $\begingroup$ I mean anything that is not in the conclusion of the pumping lemma. $\endgroup$ – Michal Adamaszek Dec 5 '18 at 9:24
  • $\begingroup$ @MichalAdamaszek Do you want to put a reference in support of your claim? As far as my understanding goes, if I take $y$ to be of odd length, it does not violate the acceptable conditions for $y$. $\endgroup$ – Masroor Dec 5 '18 at 9:39
  • $\begingroup$ What do you mean by "you take y"? You get y from the pumping lemma, and not choose it yourself. I am referring to how you use the pumping lemma to prove a language is not regular. Are you trying to do something else? $\endgroup$ – Michal Adamaszek Dec 5 '18 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.