0

I don't think that I fully understand how to use the pumping lemma to prove that a given language is not regular. I'm reading Sipser and according to him the definition of the pumping lemma is:

"If A is a regular language, then there is a number p ( the pumping length) where, if s is any string of A of length at least p, then s may be divided into three pieces, s = xyz, satisfying the following conditions: 1. for each $i \ge 0, xy^iz\in A$ 2. $\left| y \right| \gt 0$ 3. $\left|xy\right| \le p$

Now given the exercise:

Show that $A_1 = \{0^n1^n2^n | n\ge 0\}$ is not regular.

I assume that $A_1$ is regular and therefore can be divided into a form $s=xyz$ for $s\in A_1$. But now I could simply say that $s=0^p1^p2^p$ where p is the pumping length and divide s such that $x=\epsilon, y= 0^p1^p, z = 2^p$ and claim that because $\left|xy\right| \gt p$ it follows that $A_3$ is not regular. Similarly for the language $L=\{a^nb^la^k | k \neq n+l\}$ I could use the same logic. But all the solutions to those exercises come up with fairly complicated solutions compared to this logic, so I assume something is wrong here.

I think I misunderstand something about the theorem and how to use it to prove some language is not regular, what am I getting wrong?

eager2learn
  • 2,799

1 Answers1

2

When you use the lemma, you don't get to pick $x$, $y$, and $z$ for a given string $s$. All you know is that if the language is regular, they must exist, but not necessarily what they are. To show that a language is not regular, you need to show that for any choice of $x$, $y$, and $z$, at least one of the conditions (1), (2), and (3) fails. (Here the easiest way is probably to take a division satisfying (2) and (3) and show that (1) fails.)

Here's a hint: let $n>p$. If (2) and (3) hold, what can you say about $y$? Can you then get a string of the form $xy^kz$ that is not in the language?

universalset
  • 8,269
  • 20
  • 33
  • If $n\gt p$ I'd have to choose $x=\epsilon$ and $y=0^m, m \lt p \lt n$. In that case $y^k$ would not equal n, for all $k\ge 0$, therefore showing that the language is not regular. – eager2learn Nov 25 '13 at 19:53
  • I do have one more question. You said that I need to show that for any choice x, y, z at least one of the three conditions has to be wrong. But then you said in this case I should take a division that satisfies 2 and 3 and show that 1 fails. But if at least one has to fail, I can choose a division such that multiple conditions fail, can't I? Also do I have to list all possible divisions to show that for any choice of x, y and z the lemma does not hold? – eager2learn Nov 25 '13 at 19:58
  • In response to your first comment: This is almost correct. $x$ does not need to be empty, but $y$ would need to be some $0^m$, and then (say) $xy^2z$ would have more than $n$ zeros, but only $n$ ones. – universalset Nov 25 '13 at 20:13
  • 1
    It is certainly possible that for a given $x,y,z$ multiple conditions may fail. But since you don't get to pick $x,y,z$, you would like to know as much about them as possible -- that's why one would assume that two conditions hold and try to show that the other fails. You don't need to list out all possible choices of $x,y,z$ to do this; your proof should derive some information about $x,y,z$ from (say) conditions (2) and (3) and use that information to show that the last condition fails. – universalset Nov 25 '13 at 20:17
  • Great. Thanks a lot, you really helped me. – eager2learn Nov 25 '13 at 20:19