2
$\begingroup$

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.

Could somebody please give some advice on this?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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$? $\endgroup$
    – abc
    Commented Mar 23, 2017 at 22:53

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Alexander
    Commented Mar 24, 2017 at 19:00
  • $\begingroup$ @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 $\endgroup$
    – GoodDeeds
    Commented Mar 24, 2017 at 19:10
1
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Alexander
    Commented Mar 24, 2017 at 13:59
  • $\begingroup$ 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. $\endgroup$
    – E.D.
    Commented Mar 24, 2017 at 14:01
  • $\begingroup$ 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. $\endgroup$
    – Alexander
    Commented Mar 24, 2017 at 14:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – GoodDeeds
    Commented Mar 24, 2017 at 14:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – E.D.
    Commented Mar 24, 2017 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.