Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
Hint: use closure properties of regular languages. –  Zach Langley Dec 6 '12 at 1:59
    
Is this an exercise? What have you tried? –  Raphael Dec 6 '12 at 6:11
    
see cs.stackexchange.com/questions/6893 –  A.Schulz Dec 12 '12 at 19:53
add comment

2 Answers

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..]

share|improve this answer
add comment

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}}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.