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$
7
  • $\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$ 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$ 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.