How can I prove if this language is regular or not?

Question

How can I prove if this language is regular or not?

L = {aⁿ bⁿ: n≥1} union {aⁿ bⁿ⁺²: n≥1}

Answer 1

You could just use the pumping lemma for regular languages. It basically says that if you can find a string for any given integer n and any partition of this string into xyz such that |xy| <= n, and |y| > 0, then you can pump the y part of the string, and it has to stay in the language, that means, if xy^iz it's not in the language for some i, then the language is not regular.

The proof goes like this, kind of a adversary proof. Suppose someone tells you that this language is regular. Then ask him for a number n > 0. You build a convenient string of length greater than n, and you give to the adversary. He partitions the string in x, y z, in any way he wants, as long as |xy| <= n. Then you have to pump y (repeat it i times) until you find a string that is not in that same language.

In this case, I tell you: give me n. You fix n. The I tell you: take the string "a^n b^{n+2}", and tell you to split it. In any way that you can split this string, you will always have to make y = a^k, with k > 0, since you are force to make |xy| <= n, and my string begins with a^n. Here is the trick, you give the adversary a string such that any way he can split it, he gives you a part that you can pump. So now we pump y, let's say, 0 times, and you get "a^m b^{n+2}" with m < n, which is not in your language. Done. We can also pump a 1 time, n times, n! factorial times, anything you need to make it leave the language.

The proof of this theorem goes around saying that if you have a regular language then you have an automaton with n states for some fixed n. If a string has more than n characters, then it must go through some cycle in your automaton. If we name x the part of the string before entering the cycle, and y the part in the cycle, it's clear that we can pump y as many times as we want, because we can keep running on the cycle as many times as we want, and the resulting string has to be in the language, because it will be recognized by that automaton. To use the theorem to prove for non-regularity, since we don't know how the supposed automaton will be, we have to leave to the adversary the choose for n and for the position of the cycle inside the automaton (there will be no automaton, but you say to the adversary something like: dare to give me an automaton and I will show you it cannot exist.)

Answer 2

I'll give an approach and a sketch of a prove, there might be some holes in it that I believe you can fill yourself.

The idea is to use nerode's theorem - show that there are infinte number of equivalence groups for R_L - and from the theorem you can derive that the language is irregular.

Define two types of sets:

1. G_j = {aⁿb ^k | n-k = j , k≥1} for each j in [-2,-1,0,1,...]
2. H_j = {a^j } for each j in [0,1,...]
3. G_illegal = {0,1}^* / (G_j U H_j) [for each j in the specified range]

It is easy to see that for each x in G_illegal, and for each z in {a,b}^*: xz is not in L.

So, for every x,y in G_illegal and for each z in {a,b}^*: xz in L <-> yz in L.

Also, for each z in {a,b}^* - and for each x,y in some G_j [same j for both]:

• if z contains a, both xz and yz are not in L
• if z = b^j, then xz = aⁿ b^k b^j, and since k+j = n - xz is in L. Same applies for y, so yz is in L.
• if z = b^j+2, then xz = aⁿ b^k b^j+2, and since k+j+2 = n+2 - xz is in L. Same applies for y, so yz is in L.
• otherwise, x is bⁱ such that i≠j and i≠j+2, and you get that both xz and yz are not in L.

So, for every j and for every x,y in G_j and for each z in {a,b}^*: xz in L <-> yz in L.

Prove the same for every H_j using the same approach.

Also, it is easy to show that for each x G_j U H_j, and for each y in G_illegal - for z = b^j, xz is in L and yz is not in L.
For x in G_j, and y in H_i, for z = ab^j+1 - it is easy to see that xz is not in L and yz is in L.
It is easy to see that for x,y in G_j and G_i respectively or x, y in H_j, H_i - for z = b^j: xz is in L while yz is not.

We just proved that the sets we created are actually the equivalence relations for R_L from nerode's theorem, and since we have infinite number of these sets, each is an equivalence relation for R_L [we have H_j and G_j for every j] - we can derive from nerode's theorem that the language L is irregular.