1
$\begingroup$

Can anyone give an example of two non-regular languages $A, B \subseteq \{0, 1\}^∗$ for which the language $AB$ is regular?

$\endgroup$
  • $\begingroup$ maybe there are none? but dont see an obvious proof.... hmmm, maybe something like, if either language cannot be characterized by the pumping lemma, then neither can the concatenation? $\endgroup$ – vzn May 15 '15 at 3:20
  • $\begingroup$ What have you tried? What are your thoughts? Where did you get stuck? We want to help you understand, not do your exercise for you, and we expect you to make a serious effort on your own before asking. What non-regular languages do you know? Have you tried letting $A$ be some non-regular language you know, and then seeing if you can find a choice for $B$ that will work? $\endgroup$ – D.W. May 15 '15 at 4:25
  • $\begingroup$ Solutions can be found at "Is $A$ regular if $A^2$ is regular?" and "Are the non-regular languages closed under reverse, union, concatenation, etc?". $\endgroup$ – Hendrik Jan May 15 '15 at 8:53
4
$\begingroup$

Hint: Let $C$ be the language of words that have the same number of 1's as 0's. Is $C$ regular? Let $A = \{0,1\}^* \setminus C$. Is $A$ regular? Now, can you find a non-regular language $B$ that will make $AB$ regular?

$\endgroup$

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