Is L = {a^n b^m | n>m} a regular or irregular language?

Question

How can I prove if L = {a^n b^m | n>m} is a regular or irregular language?

Answer 1

L = {aⁿ b^m | n > m} is not a regular language.

Yes, the problem is tricky at the first few tries.

The pumping lemma is a necessary property of a regular language and is a tool for a formal proof that a language is not a regular language.

Formal definition: The Pumping lemma for regular languages

Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three sub-strings), satisfying the following conditions:

1. |y| ≥ 1
2. |xy| ≤ p
3. for all i ≥ 0, xyⁱz ∈ L

Suppose, if you choose a string, W = aⁿ b^m where (n + m) ≥ p and n > m + 1. The choice of W is valid, but this choice you are not able to show that the language is not a regular language. Because with this W, you always have at least one choice of y=a to pump new strings in the language by repeating a for all values of i (for i =0 and i > 1).

Before I am writing my solution to prove the language is not regular. Please understand the following points and notice: I made every string w bold and all i in the formal definition of the pumping lemma above.

• Although with some sufficiently large W in the language, you are able to generate a new string in the language, but not possible *with all! There are many possible choices for W (below in my proof). With that, you can't find any choice of y to generate a new string in the language for all i >=0. So because every sufficiently large W is not able to generate a new string in the language, hence the language is not regular.

Read: What does the pumping lemma formal definition say

Proof: using the pumping lemma

Step (1): Choose a string W = aⁿ b^m where (n + m) ≥ p and n = m + 1.

Is this choice of W valid according to pumping lemma?

Yes, such a W is in the language because the number of a = n > number of b =m . W is in the language and is sufficiently large >= p.

Step (2): Now chose a y to generate a new string for all i >= 0.

And no choice is possible for y this time! Why?

First, it is essay to understand that we can't have the b symbol in y, because it will either generate new strings out of the pattern or in the resultant string, the total number of b will be more than the total number of a symbols.

Second, we can't chose y = some a's, because with i=0 you would get a new string in which the number of a s will be less than the number of *b*s, and that is not possible in the language.(remember the number of as in W was just one more than b, so removing any a means in the resultant string N(a)=N(b) that is not acceptable because n>m.)

So if we could find some W, those are sufficiently large, but using that we can't generate a new string in the language that contradict with the pumping lemma property of a regular language, hence then the language {aⁿ b^m | n > m} is not a regular language indeed.

Answer 2

The language is regular. In the answer by Grijesh Chauhan, his mistake was that in step 2 he chose a string that b^m > a^n.

That is fine, but when we pump, we get a string that doesn't follow this rule, but it is still in the language. For example, choose a^P and b^(P+3) where P = 3. We get aaabbbbbb. If we do the x(y^i)z proof, we get x = aa , y = a , z = bbbbbb. Now i can be any number, let’s say 10. The string is now aaaaaaaaaaaabbbbbb. This string doesn't follow the rule we set (b^m > a^n), but it is still in the language. So therefore we can't prove the string is nonregular.

Also, we can create an NFA from this expression, so it must be regular.

Image of an NFA