Prove language irregular with pumping Lemma

Question

I am trying to prove that the following language is not regular using the pumping lemma

L= { a^i b^j | i^2 > j}

Any tips on this? I am completely stuck.

Thanks.

Answer 1

The pumping lemma says: If a language A is regular => there is a number p (pumping length) where, if s is any string in L such that |s| >= p, then s may be divided into three pieces s=xyz, satisfying the following condition:

1. xyⁱz is in L for each i>=0
2. |y|>=0
3. p>=|xy|

The right way to show that a certain language L is not regular is to suppose L regular and try to reach a contradiction.

Lets try to demonstrate that L = {0ⁿ1ⁿ}|n>=0} is not regular. We start assuming to the contrary that L is regular.

You can think about this kind of demonstration as a game:
Challenger: He choose the pumping length p. You cannot do any presumption on it.
You: Now it is your turn: choose the "kind" of string that represents the irregularity of the language.
Lets say that the string is in the form 0^p1^p.
A good tip in this step is to try to limit the adversary next move.
Challenger: He presents to you a string s in the form 0^p1^p.
You: It's time to pump! If you chose correctly the form of the string in your previous move, you can do some assumption.
In our case, for example, we know that the substring y consists only of 0s (at least one 0 because |y|>0), because |xy|<=p and first p-elements are 0s.

Now we show that it exists i>=0 such that xyⁱz is not in L. For example, for i=2 the string xyyz has more 0s than 1s and so is not a member of L. This case is a contradiction. => L is not regular.

Never forget to demonstrate why the pumped string cannot be a member of L.

If you have any doubt, feel free to ask :)

Cheers.

Answer 2

To the above answer, "The pumping lemma says: If a language A is regular => there is a number p (pumping length) where, if s is any string in L such that |s| >= p, then s may be divided into three pieces s=xyz, satisfying the following condition:"

You mean "If a language L is regular"

Also, the three conditions
1. xy^iz is in L for each i>=0
2. |y|>=0
3. p>=|xy|

The second should be just |y| > 0 not >=

Answer 3

Say you choose the string:

a^2b^5

aabbbbb. Which is in the language.

Now your opponent can choose XYZ.

Their options: 1.) X(empty)Y(some a's) 2.) X(some a's)Y(some a's and some b's) 3.) X(some a's)Y(some a's)

Based on their possible choices, you pump up Y using Y^i where i is an arbitrary number of your choice.

Say they choose 1.)

X(-)Y(a)Z(abbbbb)

If you "pump" up Y^i choosing i = 0. The new string becomes abbbbb. Which is not in the language.

Repeat this for each possible choice of the opponent, if you can pump up Y in a way that produces a string that is not in the language L, then you've succeeded in proving that the language is not regular.