1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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$ I'm not sure what you are referring to. $\endgroup$ – Yuval Filmus Sep 24 '18 at 1:06
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.