# Proof that a language is not regular

as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \{w\in \{a,b,c\}^* \; | \enspace z(a,w) = z(b,w) + z(c,w)\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m>1$ so that $|w| \geq m$ is fulfilled. I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| \leq m$ and $|y| > 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

• You have picked a good $w$. Now choose a $i \in \{0,2,3,4,5,...\}$ (just one value for $i$ is enough). what can you conclude about $xy^iz$? – abc Mar 23 '17 at 22:53

After taking $w=a^{2m}b^mc^m$, you now need to show that irrespective of how you split $w$ into $x,y,z$, at least one of $|xy|\le m$, $|y|\gt0$ and $\forall i, xy^iz\in L$ is false.

To do this, you try to split it such that all three do hold, and show that you cannot do so.

For any split in which $|xy|\gt m$ or $|y| = 0$, one of the three is already false, and we are done. Now, suppose that both of these are true. Then, as the first $2m\gt m$ characters of your strings are $a$s, and $|xy|\le m$, you can conclude that $x$ and $y$ must contain entirely of $a$s, if they have non-zero length. As $|y|\gt 0$, $y$ contains at least one $a$.

Suppose $y$ consists of $k$ $a$s. Then, take $i=2$, which gives $xy^2z\in L$. The new string will be thus $a^{2m+k}b^mc^m$. But this cannot lie in $L$, and we have a contradiction. How ever you try to split $w$, you will always fail to satisfy at least one of the conditions. Then, you can conclude that $L$ is not regular.

Note that you cannot choose how you want $x,y,z$ to be. The pumping lemma only assures the existence of $x,y,z$ satisfying the conditions. Your inability to find one combination does not prove that it doesn't exist; you need to show it explicitly.

• Thanks for the clarification regarding the random choosing of $x$, $y$ and $z$. If $k$ denotes the number of $a$s in $y$, then $y$ would have to be empty for $k = 0$ in the initial word, right? That would violate the restriction that $y$ must not be empty. Or am I wrong? – Alexander Mar 24 '17 at 19:00
• @Alexander Yes, because $|y|\gt0$ would not be satisfied. If this is the case, we are done. Else, assume $k\gt0$, and the rest of the argument holds – GoodDeeds Mar 24 '17 at 19:10

You've almost solved it already. You need to define which part of your word x, y, and z represent, and the obvious partition works well here. You know, by the pumping lemma, that you can repeat y any number of times, and the new word will still be in the language.
In this case, repeat y twice. Is the resulting word still a member of the language?

• Can I say that $xy = a^m$ and assume $x = a^0$ and $y = a^m$ or does that restrict my proof?If that is okay, I would take $i = 2$, so I have $w_2 = xy^2z$. Then I would say that $w_2 = a^{3m}b^mc^m$. The word $w_2$ would then not be part of my language $L$. Is this correct or am I on the wrong path? – Alexander Mar 24 '17 at 13:59
• That should work, but I'd have made x be all the a's, y be all the b's, c be all the z's. – E.D. Mar 24 '17 at 14:01
• Thanks for the response. I I change it to match your suggestion, I would have to change my word also, because $|xy| <= m$ must be fulfilled. – Alexander Mar 24 '17 at 14:05
• You cannot choose what you want $x,y,z$ to be, you need to show that no split of $w$ into $x,y,z$ can satisfy all the statements of the pumping lemma to show that the language is not regular. – GoodDeeds Mar 24 '17 at 14:25
• GoodDeeds is right. I thought the pumping lemma said that every xyz combination could be pumped, but it says there exists an xyz that can be pumped. – E.D. Mar 24 '17 at 14:37