Prove or disprove the following statement If L1 L2 is regula

Prove or disprove the following statement: If L1 L2 is regular, then L1 and L2 are both regular.

Solution

Let L = L1 L2. If L is regular and L2 is regular, L1 must be regular. FALSE. We know that the regular languages are closed under intersection. But it is important to keep in mind that this closure lemma (as well as all the others we will prove) only says exactly what it says and no more. In particular, it says that: If L1 is regular and L2 is regular Then L is regular. Just like any implication, we can’t run this one backward and conclude anything from the fact that L is regular. Of course, we can’t use the closure lemma to say that L1 must not be regular either. So we can’t apply the closure lemma here at all. A rule of thumb: it is almost never true that you can prove the converse of a closure lemma. So it makes sense to look first for a counterexample. We don’t have to look far. Let L = . Let L2 = . So L and L2 are regular. Now let L1 = {ai : i is prime}. L1 is not regular. Yet L = L1 L2. Notice that we could have made L2 anything at all and its intersection with would have been . When you are looking for counterexamples, it usually works to look for very simple ones such as or *, so it’s a good idea to start there first. works well in this case because we’re doing intersection. * is often useful when we’re doing union.