I have a language $L$:
$$L = \{w : a^ib^j; i > j \}$$
I need to prove this language is not regular using Pumping Lemma. I'm wondering if I'm doing it correctly:
I need to find a suitable $w$, where $|w| \geq p$ (the pumping length). I choose:
$$w = a^{(p + 1)}b^p$$
This string can be broken up into $3$ substrings ($x, y$ and $z$), where $|y| > 0$.
For all $k \geq 0$, If the string $y$ can be 'pumped' $k$ times, and still be in the language, it is a regular language.
So I need to prove it is not regular by finding a counter example, $k = 2$:
$$xy^2z = a^{(p + 1)}b^{(p + |y|)}$$
Since $p + 1$ is not greater than $p + |y|$, then $L$ is not a regular language.
Would this be enough to prove that the language is not regular? Here, I assumed that $|y|$ could be $1$, since the number of $a$'s is a minimum of $1$.
Best Answer
No, this isn't enough to prove that the language is not regular. You have to take into account all the possible options for $y$. As I can see you consider $y$ contains only $b$'s. You should add the cases:
i) $y$ contains both $a$'s and $b$'s then in the word $xy^kz$ for any $k\geq 2$ there would be switching of $a$'s and $b$'s. For instance, if $x=aa,y=ab,z=b$ then $xy^2z=aaababb$ which isn't in $L$.
ii) $y$ contains only $a$'s, then for $k=0$ the number of $a$'s is less than the number of $b$'s in the word $xz$. So $xz$ isn't in $L$.