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
- $s = xyz$
- $ |y| \ge 1 $ and $ |xy| \le n $
- $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$