Question

Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m < n-2 isn’t regular.

(I'm using the ^ notation but your free to make yours b^maⁿ instead of (b^m)(a^n) )

Use the pumping lemma for regular languages.

Answer 1

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

Proof: using pumping lemma

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

Is this choice of W is valid according to pumping lemma?

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

Step (2): Now chose a y to generate 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 b symbol in y because it will either generate new strings out of pattern or in resultant string total number of b will be more than 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 number of a s will be less then number b s that is not possible in language.(remember number of a in W was just one more then b so removing any a means in resultant string N(a)=N(b) that is not acceptable because n>m)

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

Hence, L = (b^maⁿ) , 0 ≤ m < n-2 isn’t regular also.