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.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
answered Sep 23 '18 at 3:36
-
$\begingroup$ The definition of says n>k or n!=(k-1). Why wouldn't we include the cases where n<(k-1)? $\endgroup$ – aky Sep 23 '18 at 23:45
-
$\begingroup$ ignore the previous question, but can you tell me how to go from reduced language to regular expression you mentioned. Thanks. $\endgroup$ – aky Sep 24 '18 at 0:48
-
-
$\begingroup$ 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. $\endgroup$ – aky Sep 24 '18 at 1:10
-
$\begingroup$ Definitely not. I looked at $a(a^*b^*\setminus L) \cup \{\epsilon\}$. $\endgroup$ – Yuval Filmus Sep 24 '18 at 1:11
