proving not regular with pumping lemma

214 Views Asked by At

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.?

1

There are 1 best solutions below

9
On BEST ANSWER

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$.