Not quite sure if I understand pumping lemma correctly.

so if i have this language and i like to show it is not regular:

L={ $q^a w^be^c| a,b,c \in N, a+b=c$}.

If L would be regular, than there must be an pumping length n. I use string s= $q^n w^ne^{2n}$ which is in L. No matter if y is just q,w or o, s=$xy^iz$ will never be in L (because of a+b not c). y cannot have q's,w's or w's and c's, because s=$xy^iz$ not of form $q^n w^ne^{2n}$. So L is not regular.?


Your explanation is a little hard to follow, but it appears to be basically correct. The key point is that $|xy|\le n$ and $|y|\ge 1$, so that $y=q^k$ for some $k\ge 1$. But then


and $n+(i-1)k+n=2n+(i-1)k$ is equal to $2n$ if and only if $i=1$. Thus, if $i\ne 1$, then $xy^iz\notin L$.

  • $\begingroup$ So |xy|≤n means that z can be the empty string? And |y|≥1 that y needs to have at least one edge? But why choosing y=q^k and what is happening after that? n+(i−1)k+n=2n+(i−1)k this I understand, but the part before? Many thanks $\endgroup$ – SOAP Jun 1 '16 at 18:15
  • $\begingroup$ @SOAP: The pumping lemma says that if $n$ is the pumping length, and $|s|\ge n$, then $s$ can be decomposed as $xyz$ in such a way that $|xy|\le n$, $|y|\ge 1$, and $xy^iz\in L$ for each $i\ge 0$. The second condition means that $y$ cannot be empty, and therefore the words $xz,xyz,xy^2z,xy^3z,\ldots$ are all distinct. Either $x$ or $z$ can be empty, though this will not happen with your $s=q^nw^ne^{2n}$: here $xy$ must be a substring of $q^n$, since $|xy|\le n$, so $z$ includes at least $w^ne^{2n}$, and possibly some of the $q$s as well. The fact that the lemma guarantees a decomposition ... $\endgroup$ – Brian M. Scott Jun 1 '16 at 18:20
  • $\begingroup$ ... with $|xy|\le n$ means that $xy$ is a substring of the initial $n$ characters, so that there must be integers $\ell\ge 0$ and $k>0$ such that $x=q^\ell$ and $y=q^k$. Then $z=q^{n-\ell-k}w^ne^{2n}$. $\endgroup$ – Brian M. Scott Jun 1 '16 at 18:21
  • $\begingroup$ I guess my problems are lying with |xy|≤n. I don't understand, why this implies that xy must be a substring of q^n. $\endgroup$ – SOAP Jun 1 '16 at 18:42
  • $\begingroup$ @SOAP: Suppose that $|xy|=m$, i.e., that $xy$ has $m$ characters. Since $s=xyz$, this means that $xy$ is the substring of $s$ consisting of the first $m$ characters of $s$. The pumping lemma says that $m\le n$, and the first $n$ characters of $s$ are all $q$, so every character of $xy$ must be a $q$. $\endgroup$ – Brian M. Scott Jun 1 '16 at 18:46

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.