Prove that the language L is not a regular language, using pumping lemma

Question

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$.

Answer 1

I think I found the answer.

|xy| can be at most $p$, so it also contain only $a$'s. For this string, setting $i=0$ will make it: $a^{p+1-|y|}b^p$. Since |y| must be $|y| > 0$, then the length of the first a's is at most $p$. Given this, number of a's is Not greater than number of b's. Therefore I have found a string $w$ that does not hold the pumping lemma conditions for all $p >= 1$, therefore $L$ is not regular.

Answer 2

I failed to follow your proof. May be it is correct I can't tell, sorry.

Let me explain how I would prove the statement.

Our language $L$ consists of all the strings $a...ab...b$ such that number of $a$'s is bigger than number of $b$'s. Suppose the language is regular, that is there is an automaton (Deterministic Finite Automaton) which accepts only the strings having this property. Let $n$ be the number of states in this automaton.

Now let's take a string $a^{3n}b^{2n}$ and feed it to our automaton. The automaton accepts the symbols one by one and after each accepted symbol changes it's state - that's how automaton works.

While accepting the last 2n $b$ symbols our automaton must have to visit some state at least twice. Because there are fewer states than the number of accepted symbols. It happened that our automaton accepted several $b$ symbols and returned to the same state. Fine, immediately after that we can insert as many such sequences of $b$ symbols as we want into our string. After each of the inserted sequences our automaton would return to the same state. After several inserted sequences the automaton would accept the rest of the string and eventually accept our string $a...ab....b$ where the number of $b$ is arbitrary large.

So, we constructed the string which is not in $L$, but is accepted by our automaton. We failed to construct automaton which accepts only the strings in $L$. That means $L$ is not regular.

Answer 3

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$.