union of regular language and non regular language

Question

I have the languages $L_1 = 00^*\{1^n0^n \mid n \geqslant 0\}$ and $L_2 = 0^*1^*$. I know that $L_1$ is not regular and $L_2$ is. But is $L = L_1 + L_2$ is not regular? An extended explanation will be much appreciated :)

Answer 1

Let $L_3$ be the regular language $01^+0^+$. If $L_1 + L_2$ were regular, then $(L_1 + L_2) \cap L_3$ would also be regular. Now $$ (L_1 + L_2) \cap L_3 = 0\{1^n0^n \mid n > 0\} $$ which is not regular.

Answer 2

The strings in the language $L_1 \cup L_2$ take one of the following two forms:

• $00^k1^n0^n$
• $0^k1^n$

We know that the strings in the first case are irregular, but as soon as we see a $0$ after a $1$ (which is a regular thing to check), we know we must be in the first case. This is some heuristic evidence that $L_1 \cup L_2$ isn't regular.

How can we make this formal?

Well, let's fix a supposed DFA for $L_1 \cup L_2$. What would it have to do with the inputs $01, 011, 0111, 01111, \ldots$?

By the pigeonhole principle, we must have $01^i$ and $01^j$ end up in the same state (since there are only finitely many states the machine can be in, but there are infinitely many strings of the form $01^n$).

But if $01^i$ and $01^j$ are in the same state, then $01^i0^i$ and $01^j0^i$ are also in the same state.

Now we see the problem - is this an accepting state? If it is, then we accidentally accept $01^j0^i$, which isn't in the language. If it isn't, then we accidentally omit $01^i0^i$, even though it is in the language. So no DFA properly accepts $L_1 \cup L_2$, and it is irregular.

The important thing to notice, and what I was trying to bring to your attention in the comments, was that unioning $L_1$ with $0^*1^*$ has no way of helping you! We can easily identify if we're in $L_1$ or $L_2$ based on the form of the string. As soon as we've read a $0$ after a $1$, we know the only strings that have a chance of being accepted are those in $L_1$, and so the exact argument that shows $L_1$ is irregular also shows that $L_1 \cup L_2$ is irregular!

---

I hope this helps ^_^