1
$\begingroup$

I have been trying to understand Pumping lemmas for a while now, I am doing this exercise and I think that the pin has finally dropped. However, I am unsure if I am doing it even remotely correctly. I will briefly explain my attempt and thus my solution. Thereafter I would discuss a few points that are not as clear to me just yet. The exercise is the same as in the title. Here is my solution, but in-case you have forgotten:

Prove that $L_1 = \left\{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\right\}$ is not regular using Pumping lemma

So, in order to show that a language is not regular, we first must assume it to be regular (in-order to be able to use pumping lemma). If $L_1$ is regular, then there exists a constant $n$ such that $ s \in L_1 $ and $ |s| \ge n$ implies that there is a string $xyz$ satisfying

  1. $s = xyz$
  2. $ |y| \ge 1 $ and $ |xy| \le n $
  3. $xy^iz \in L1 $ for all $ i \ge 0 $

We'll try to extract a contradiction. This is how I did it
I first create a string such that $ m + k = n $, my string was $0^1 1^1 2^2$ or just $0 1 2 2 $ I then split this string into three parts $ x y z $ so that $x = 0 \\ y = 1 \\ z = 22$

I then selected $ i \Rightarrow 2 $ which gives us , by the third rule, $ xy^2z $. This gives us the string
$ 01122 \notin L1 $ because $1 + 2 \neq 2 $

That is my solution, I hope you could understand it. Now to my discussion points:
As you see, I have provided a contradiction, which should be enough. However, what I also want to know is that in other exercises , say $\{\, a^n b^n \,|\, n \ge 1 \,\}$ you select a Pumping length $P$ and then typically get a string that is $a^p b^p$ i.e say that $ P = 3 $ you'd get $aaabbb $ AND then you divide into strings, but since the powers are all different in my exercise, picking a $P$ would not be as helpful, right?

Is it possible to select a Pumping length $P$ here too? Do I need to check the other conditions as well? As I understand it, a language is proven non-regular if it can't satisfy all of the requirements at the same time.

To clarify the question, when I meant 'how do I apply $P$'? I meant, how do I apply to the already existing powers ($m$, $k$ and $n$). Do I simply attach P to each power which would make it $ 0^{PM} 1^{PK} 2^{PN} $ ? A follow-up question: When I select $P$, must I then also select $M$, $K$ and $N$? So say I select $ P = 3 $ , should I also select $M = 1$, $K = 1$ and $N = 2$?

Thanks to the guy down under I know understand how to select a string ($ 0^p 1^p 2^2p $) for instance. But, then I don't know how to split the string. Can do it like this:

$x= 0^r$ , $y=0^{p-r}1^t$ and $z = 1^{p-t}2^{2p} $? Would this string be in the language ? I assume it would be as $xyz = 0^p 1^p 2^{2p} $ BUT Idk, I might be doing it all wrong

Then if I select $i = 2$ so $xy^2z$ I would get $xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{p-t}2^{2p} = 0^{2p-r}1^{p + t}2^{2p} \notin L$ Thus our contradiction, is this correct thinking then?

To answer the guy below:
Assume $L$ is regular, then there exist a constant $p$ such that $ s \in L$ and $|s| \ge p$ implies that there exist string $xyz$ satisfying following:
$1) s = xyz$
$2) |y| \ge 1$ and $|xy| \le p $
$3) xy^iz \in L$ for very $i \ge 0$

(Which answers your first question)
We pick our string $s = o^p 1^p 2^{2p}$ as the property of a string in a language must be $m + k = n $ $ (p + p = 2p)$
We then split the string into three parts $xyz$ , I am going to split them differently to you. $x = 0^p$ $ y = 1^p $ and $z = 2^{2p} $ if we then select $ i = 2$ we get $xy^2z = 0^p 1^{2p} 2^{2p} \notin L $ BECAUSE $ 1 + 2 \neq 2$

$\endgroup$
  • 1
    $\begingroup$ Please do not insert "Edit" into your post, try seamless integration instead, people who have read it will know that something was changed (or look at edit history), people who will read it fir the first time will find it less confusing if your post is one piece. $\endgroup$ – Evil Oct 24 '17 at 20:22
1
$\begingroup$

For your choice of $s=0^11^12^2$, the pumping lemma might not apply. Remember, assuming that the language is regular means that there is an (unknown) integer $p$ such that the pumping lemma applies to every string of length $p$ or more. You don't know what $p$ is: if it were, say, 6 then since $|s|=4$ the PL simply wouldn't apply to your string and you could draw no conclusion.

That's why the strings chosen for pumping almost invariably involve $p$: it's there to assure that no matter what $p$ was, the pumped string would be at least $p$ characters long. For your example, you could choose $0^p1^p2^{2p}$ or $0^p1\,2^{p+1}$ or $0^p2^p$ even something like $0^{p^2}1^{2p+1}2^{(p+1)^2}$.


Here's what a PL proof of this result looks like, with some bits for you to fill in: Assume the language $L$ is regular. Choose $s=0^p1^p2^{2p}\in L$, where $p$ is the integer of the pumping lemma (why can we say the PL applies to $s$?). Then if we write $s=xyz$ as in the PL, we'll have $y=0^t$ for some $0<t\le p$ (why?) and then $xy^2z\notin L$ (why?), a contradiction (why?).


The proof without the PL is an example of a more or less common idiom: using closure properties. If $L$ were regular, then $L\cap 0^*2^*$ would be also, since regular languages are closed under intersection. However $$ L\cap 0^*2^*=\{0^n2^n\mid n\ge 0\} $$ (since we set $k=0$ when doing the intersection) but we know that that language isn't regular, so we have a contradiction and hence $L$ must not be regular.

$\endgroup$
  • $\begingroup$ my proposed solution is edited into the original post. Please check it. I do think I understand this now. Also if your y = 0^t , and assume x = 0^r then z would be = 0^p-t-r 1^p 2^2p because, z would include rest of the string. Right? $\endgroup$ – Hoaz Oct 25 '17 at 13:45
  • $\begingroup$ another comment. So I just realized my solution above does not take |xy| <= p into account. As when I divide my x = 0^p, y = 1^p, z=p^2p this makes |xy| >= p, thus not satisfying the third condition. HOWEVER if I were to do, like you suggested x=0^r, y=0^t, z=0^p-t-r 1^p 2^2p, |xy| is then <= p. This is correct thinking, yes? $\endgroup$ – Hoaz Oct 25 '17 at 15:27
  • $\begingroup$ @Hoaz. Yes to both of your comments. $\endgroup$ – Rick Decker Oct 25 '17 at 17:14
  • $\begingroup$ thanks mate! Clears some things up! I think I have got this in the bag :) Aside from my mistake with the |xy|>= p, my solution above should be correct. I.e. it does show a contradiction. $\endgroup$ – Hoaz Oct 25 '17 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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