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

To prove that L is not a regular language, we will use a proof by contradiction. Assume that L is a regular language. Then by the Pumping Lemma for Regular Languages, there exists a pumping length p for L such that for any sring s ∈ L where |s| ≥ p, s = xyz subject to the following conditions:

(a) |y| > 0

(b) |xy| ≤ p, and

(c) ∀i > 0, xyⁱ z ∈ L.

Choose s = bpap . Clearly, |s| ≥ p and s ∈ L. By condition (b) above, it follows that x and y are composed only of zeros. By condition (a), it follows that y = bk for some k > 0. Per (c), we can take i = 0 and the resulting string will still be in L. Thus, xy0 z should be in L. xy0 z = xz = b(p−k)ap . But, this is clearly not in L. This is a contradiction with the pumping lemma. Therefore our assumption that L is regular is incorrect, and L is not a regular language.