L = {a n b m | n> m} is not a regular language.
Yes, the problem is complicated , first try and deserve a vote.
Pumping Lemmas a necessary property of a regular language is a tool for formal proof that a language is not a regular language.
Formal Definition: Pumping Lecture for Common Languages
Let L be the correct language. Then there exists an integer p ≥ 1, depending only on L, such that each row w in L of length at least p (p is called the "pump length") can be written as w = xyz (i.e., w can be divided by three substrings) satisfying the following conditions:
- | at | ≥ 1
- | x | ≤ p
- for all i ≥ 0, xy i z ∈ L
Suppose if you select the line W = a n b m where (n + m) ≥ p and n > m + 1 . The choice of W is valid, but this choice , which you cannot show, is not a language. Since in this case W you always have at least one choice y=a for pumping new lines in the language, repeating a for all values of i (for i = 0 and i> 1).
Before writing your solution for proof, the language is not regular. Please understand the following points and note: I made bold every string w and all i in the formal definition of the pumping lemma above.
- Although with some Large enough W in the language you can generate a new line in the language, but NOT WITH WITH ALL ! There are many possible options for W (below in my proof) so that you cannot find any choice y to generate a new line in the language for all i> = 0 . So each Big enough W cannot generate a new line in the language, so the language is NOT regular.
read: what the formal definition of the lemma of leverage says
Proof: using the pump lemma
Step (1): Select the line W = a n b m where (n + m) ≥ p and n = m + 1 .
Is this choice of W is valid according to pumping lemma?
Yes, such a W is in the language, because the number a = n the number b = m. W in the language and large enough> = p .
Step (2): Now select y to create a new line for all i >= 0 .
And no choice is possible for y this time! What for?
Firstly, this is an essay to understand that we cannot have the character b in y, because it either generates new lines from the template, or in the final line, the total number b will be greater than the total number a characters.
Secondly, we cannot choose y = some a , because with i=0 you get a new line in which the number a s will be less than the number b s, which is impossible in the language. (remember that the number a in W was just another b character, so any means in the resulting string N (a) = N (b) was deleted, which is unacceptable, since n> m)
Thus, we could find some W that are large enough, but using this we will not be able to generate a new line in the language that contradicts the property of the regular language pump lemma, therefore, then the language {a n b m | n> m} is not an ordinary language.