# proving not regular with pumping lemma

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
$$xy^iz=q^{n+(i-1)k}w^ne^{2n}\;,$$
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$.
• @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 ... – Brian M. Scott Jun 1 '16 at 18:20
• ... 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}$. – Brian M. Scott Jun 1 '16 at 18:21
• @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$. – Brian M. Scott Jun 1 '16 at 18:46