Show that the language of strings not in the union of two regular languages is regular

Question

Given languages $L_1,L_2$, defines $X(L_1,L_2)$ by

$\qquad X(L_1,L_2) = \{w \mid w \not\in L_1 \cup L_2 \}$

If $L_1$ and $L_2$ are regular, how can we show that $X(L_1,L2)$ is also regular?

Answer 1

There are several ways to show that a language is regular (check the question How to prove a language is regular?)

Specifically for the language in your question, start with DFAs for $L_1$ and $L_2$ and try to construct an NFA for $X(L_1,L_2)$ using them. More details below:

Note that $X(L_1,L_2) = \overline{L_1} \cap \overline{L_2}$.
From the DFA of $L_1$ construct the DFA of $\overline {L_1}$ (making any final state not-final, and vice-versa). Do the same for $L_2$. Intersection of regular languages can be constructed via product machine (see this question).
[Of course, if you already know that a complement of a regular language is also regular, and so the intersection of two regular languages – you are done without constructing those DFAs..]

Answer 2

Expanding on Zach's comment, you (should) know the following things:

1. If $L_{1}$ and $L_{2}$ are regular languages, then $L_{1} \cup L_{2}$ is a regular language.
2. If $L_{1}$ and $L_{2}$ are regular languages, then $L_{1} \cap L_{2}$ is a regular language.
3. If $L_{1}$ and $L_{2}$ are regular languages, then $L_{1} \cdot L_{2}$ is a regular language.
4. If $L$ is a regular language, then $L^{\ast}$ is a regular language.
5. If $L$ is a regular language, then $\bar{L}$ is a regular language.

Now you should be able to pick a few of these that combined make up your $X$ language function/operator/whatever you call something like that (well, it's just a language defined in terms of others).

Just for some background, proofs for these properties can be found (IN A REALLY LARGE FONT) here.

Give this a go, if you're really stuck, I'll put a bit more in the spoilers below (but with little explanation).

$X(A_{1},A_{2}) = \overline{A_{1}\cup A_{2}} = \bar{A_{1}}\cap\bar{A_{2}}$.