2
$\begingroup$

I want to show that $L = \{a^n b^m a^{n+m} \mid n, m \geq 0\}$ is not regular.

Can I say that the complement of $L$ intersected with $a^*b^*$ equals $\{a^n b^n \mid n \geq 0\}$ and since I know that $\{a^n b^n \mid n \geq 0\}$ is not regular, then $L$ is not regular?

Or would I have to use the pumping lemma?

$\endgroup$
  • 3
    $\begingroup$ You can do whatever you want as long as it's logically valid. $\endgroup$ – Yuval Filmus Oct 18 '15 at 21:51
  • $\begingroup$ @YuvalFilmus Does that make sense tho? Like I guess is that true? $\endgroup$ – user270494 Oct 18 '15 at 23:10
  • 1
    $\begingroup$ That's for you to answer. Try to be more confident in your knowledge. $\endgroup$ – Yuval Filmus Oct 19 '15 at 7:05
2
$\begingroup$

That line of reasoning can work in principle; you are trying to use closure properties of REG for a proof of contradiction. Make sure you understand that that's what you're doing.

Unfortunately, you do not get $\{a^nb^n\}$. For instance, $a^3 b^4 \in \overline{L} \cap a^*b^*$. Check out our reference question for more techniques you can try.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Actually can I just use the pumping lemma and state $a^0b^pa^p$ is in the language, then y = $a^k$ with 0 < k <= p, choose i = 0 so I get $a^{−k}b^pa^p$ which is not in the language? $\endgroup$ – user270494 Oct 22 '15 at 5:46
  • $\begingroup$ @user270494 No, it wouldn't work like that. I recommend you visit our reference questions. $\endgroup$ – Raphael Oct 22 '15 at 7:35
2
$\begingroup$

Hint: What do you get when you intersect $L$ with the language denoted by $b^*a^*$? It won't be quite what you need, but it's close. You can then get the $b^ma^m$ language by subtracting (i.e., set difference) some regular language from that.

| cite | improve this answer | |
$\endgroup$

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.