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 need to find a suitable $w$, where $|w| \ge $ some $p$

$w = a^{p+1}b^{p}$

$w$ makes sense because it is in $L$ and has a length greater than $p$

We must be able to break it up into 3 substrings $xyz$ where:

$|xy| \le p$,

$|y| \ge 1$, and

$xy^iz$ is in $L$ for all $i \ge 0$

For all possible choices, which also satisfy conditions 1 and 2, we have the following cases:

Case 1: $xy$ is only composed of just $a$'s. If we pump $y$ with $i=0$, then we will end up with and equal amount of a's and b'stherefore not in the language.

Case 2: $xy$ is in both a and b parts. Therefore $y$ is some length of b's. Then if we pump $y$ with $i=2$, the number of b's will be greater than or equal to the number of a's, therefore not in the language.

Case 3: $xy$ consists of just b's. Then if we pump $y$ with $i=2$, then the number of b's will be greater than or equal to the number of $a's$, and not be part of the language.

Since we have shown that the string $w$ from $L$ cannot satisfy all 3 conditions at once for all pumping length $p \ge 1$, then $L$ is not a regular language.


1 Answer 1


You have some incorrect assumptions in your cases.

If $w = a^{p+1} b^p$ and $|xy|\le p$, then $y$ cannot contain any $b$'s. If it did, then $|xy|>p$ by the construction of $w$.

So how do we fix this? We know that $y=a^k$ for some $1 \le k \le p$, because it cannot be empty and it cannot contain any $b$'s. Now you should be able to argue that $xy^0z \notin L$, which will contradict that $L$ is regular.

  • $\begingroup$ Ah I didn't realize that. I was thinking of CFL's and my mind was somewhere else. Not sure what I was thinking lol. Thank you! $\endgroup$
    – Andrew Kor
    May 3, 2019 at 1:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .