I have a language defined by
$L = \{ a^{m}b^{n}:m,n \in N_{0}\}$
This means I have 3 cases:
- $1) \ m > n$
- $2) \ m < n$
- $3) \ m = n$
So I have to prove it in 3 different cases.
Taking case 1 where $m > n$ :
I can choose language such as
$$w = a^{p+1}b^{p}$$
Let's choose $p = 2$.
We have 3 different decompositions for $aaabb$.
$x = \varepsilon \ \text{or} \ x = a \ \text{or} \ x = \varepsilon$
$y = aa \ \text{or} \ y = a \ \text{or} \ y = a$
$z = abb \ \text{or} \ z = abb \ \text{or} \ z = aabb$
We can write it in the following way
$$a^{k}a^{l}a^{j}b^{p}$$
where $k \ge 0 , l \ge 1 , j \ge 0 $ and $ l + k \le p + 1 , l + k + j = p + 1$
Which means when I choose index $i = 0$ such as $xy^{i}z = xy^{0}z$
I have now
$$a^{k}a^{0}a^{j}b^{p}$$
and this means that
$ k + l + k \le p $ thus language $w$ does not belong to language $L$ and is not regular ( the other 2 cases are similar; i only want to check if my undertanding is correct).
It this correct or did i misunderstood any concept of pumping lemma? Also, what is the best way to choose $p$?
Thanks for answers and help!
Your argument is difficult to understand, but it seems like you are trying to show that $L$ is not regular by first considering the language $L' = \{a^mb^n \mid m > n\}$. But the problem is that while a pumped up word from $L'$ might not be in $L'$, it can still be in $L$.
To make matters worse, the langeuage $L$ is regular. Consider e.g. the regular grammar with starting symbol $L$ and the rules $L \to aL | B$ and $B \to bB | \varepsilon$.