# Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$

I need help with proving the following language is not regular: $$L = \{ a^n b^k \mid n > k \} \cup \{ a^n b^k \mid n \neq k-1 \}$$ My usual methods using pumping lemma are not getting me anywhere.

If $$n > k$$ then $$n \neq k-1$$ (since $$k-1 \not> k$$), so your language is really $$L = \{ a^n b^k \mid n \neq k-1 \}$$. If $$L$$ were regular then so would be the following language $$a(a^*b^* \setminus L) \cup \{\epsilon\} = \{ a^n b^n \mid n \geq 0 \}$$, which is known not to be regular.

• The definition of says n>k or n!=(k-1). Why wouldn't we include the cases where n<(k-1)?
– aky
Sep 23 '18 at 23:45
• ignore the previous question, but can you tell me how to go from reduced language to regular expression you mentioned. Thanks.
– aky
Sep 24 '18 at 0:48
• I'm not sure what you are referring to. Sep 24 '18 at 1:06
• After you decide that L reduced to L=$\{a^nb^k | n \neq k-1\}$, you decided that this language is the same as a^nb^n.
– aky
Sep 24 '18 at 1:10
• Definitely not. I looked at $a(a^*b^*\setminus L) \cup \{\epsilon\}$. Sep 24 '18 at 1:11