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.


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 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.