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 Answer 1

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, 2018 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, 2018 at 0:48
  • $\begingroup$ I'm not sure what you are referring to. $\endgroup$ Sep 24, 2018 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, 2018 at 1:10
  • $\begingroup$ Definitely not. I looked at $a(a^*b^*\setminus L) \cup \{\epsilon\}$. $\endgroup$ Sep 24, 2018 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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