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

Question

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

Doha

Check out the Pumping Lemma, the description will give you a huge hint regarding the answer, Good luck with your homework. – Koloski

Question is bit typical but you have not shown you work!..I answered below. hope you will find helpful. – Tumid

This question appears to be off-topic because it is about computer science, not about programming. – Kop

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.

Tumid

@NavneetSwaminath believes there is an error in your post. – Vitrine

Important to note that if even one string of length ≥ p has one value of i ≥ 0 such that x(y^i)z ∉ L then the language is not regular. Took me a minute to realize that. – Doro

@Grijesh Chauhan , why can't we chooses y=ab inbetween ? Now if we pump y then we get equal number of a's and b's – Economical

@Economical if you choose y = ab and repeats y for i times it will give you pattern like ababababab..... for i times that would be out of language. This is what I mentioned in First, point that "we can not choose symbol b in y that cause strings out of pattern" – Tumid

Ohh. Didn't notice that. Thanks for replying. – Economical

@Grijesh Chauhan Sir, can you please me in applying pumping lemma to this language ? math.stackexchange.com/questions/2420659/…. – Economical

@Economical try to find all possible values for y and repeat that, ask that question on cs.stackexchange.com – Tumid

@Grijesh Chauhan, I think pumping lemma for CFL is slightly different. We pump out 2 variables and divide the string into 5 parts . Can you please look at my explanation in comment and tell me where am I wrong ? Actually now I think that the language is CFL as we can ignore all a's and b's in the string and just compare the number of zeroes and ones which can be easily done using dcfl :O – Economical

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

Millhon

Show the NFA if you believe it exists. Or show a regular expression. But afaics, there is nothing wrong with Grijelsh's proof, since as he says, you need to be able to find a pumpable partition for any string in the language, and you cannot find one for the string a^n a b^n, which is certainly in the language. – Pyelonephritis

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Osgood