Two regular languages over the same alphabet, regular or not regular?

Question

TRUE or FALSE:

Let $L_1, L_2$ be any two regular languages over the same alphabet $\Sigma$, then the language $L=\{w\in\Sigma^* \mid w\in L_1 \text{ or } w\notin L_2\}$ is regular.

So we have to determine whether $L_1 \cup \overline{L_2}$ is regular or not.

Proof:

First attempt:

First we have to prove that a complement of a regular language is also regular: the complement of a language $L$ with respect to an alphabet $\Sigma$ such that $\Sigma^*$ is $\Sigma^*-L$. Since $\Sigma^*$ is surely regular the complement of a regular language is always regular.

Let's prove that the union of two regular languages is also regular: For example, let $\Sigma = \{a,b\}$. Assume $L_1 = \{a\}$ and $L_2 = \{b\}$ so they are regular language. Then the union: $\{a\} \cup \{b\} = \{ab\}$ is also regular. Since $\{a\}$ is regular , $\{a\}^*$ is also a regular language.

After these two proofs we can say that the statement above is True.

Second attempt:

A regular language is regular iff there is a finite state machine recognizing it. Let $L_1 = \{S_1,\Sigma,\delta_1,s_0^1, F_1\}$ and $L_2 = \{S_2,\Sigma,\delta_2,s_0^2, F_2\}$ be two automata. First we have to take the complement of $L_2$. The complement of $L_2$ is the set of states without the set of final states: $\overline{L_2} = \{S_2,\Sigma,\delta_2,s_0^2, S_2-F_2\}$. Then we can create the product automaton of the two languages which is: $L = \{S_1 \times S_2,\Sigma,\delta_1 \times \delta_2,s_0^1 \times s_0^2, F_1\ \times (S_2-F_2)\}$. The final states of the language $L = L_1 \cup \overline{L_2}$ is the set of states where $F_1$ or $S_2 - F_2$ is final. Since there exists a finite state machine that recognizes the language $L$, we can say that $L$ is a regular language.

Can somebody please correct me? Maybe I made a mistake.

Answer 1

I see several problems.

In your first part you say that, given a regular language $L$, $\overline{L}$ is regular since $\Sigma^*- L$ is also regular. This is true, but it is implicitly using the fact that regular languages are closed under difference. It is not clear if you're allowed to use that fact as a black box (since it is a more general statement than the one you're trying to prove).

In your second part you are not giving a proof. You are just showing that $L_1 \cup L_2$ is regular when $\Sigma=\{a,b\}$, $L_1 = \{a\}$ and $L_2 = \{ b \}$. What if $\Sigma \neq \{a,b\}$? What if $L_1 \neq \{a \}$? Your proof needs to work for all possible choices of $\Sigma, L_1,$ and $L_2$.

Moreover, $L_1 \cup L_2 \neq \{ab\}$ contrarily to what you claim.

Finally, you say that since $\{a\}$ is regular then so is $\{a\}^*$. This is true but it is unclear why you need this.

Answer 2

Since $\Sigma^∗$ is surely regular the complement of a regular language is always regular.

This is exactly what you want to prove! You can't use it in its own proof! If you can use the fact that $$\text{If $L$ and $L'$ are regular, then}~L\setminus L'~\text{is regular}.$$ then, for $L = \Sigma^*$ and $L' = L_2$, you get that $\overline{L_2} = \Sigma^* \setminus L_2$ is regular, since $\Sigma^*$ and $L_2$ are regular.

Also, your proof about the union of two regular languages being also regular is not correct, because you need to show that this holds for any two regular languages and not just for the specific ones that you chose ($\{a\}$ and $\{b\}$).

In general,

• If you are given a regular language, you can assume that there is a DFA or NFA or regular expression that describes it.
• To prove that a language is regular, you need to show that there is a corresponding NFA, DFA or regular expression.

Here, you are given two regular languages $L_1$ and $L_2$. Assuming you have an NFA for each, can you construct an NFA for $L_1 \cup \overline{L_2}$?

Answer 3

You can make your life here quite easy by considering that a language is regular if and only if there is a finite state machine recognizing it.

Let's say you have n regular languages $L_1$, $L_2$, ..., $L_n$. For each there is a finite state machine recognising it: Processing a string, each FSM goes through a sequence of states, and the string is part of the language if and only if we end up in an accepting state.

Now create a state machine where each state is a vector of n states of the n original state machines. We move from one state to the next by changing the i-th component of the state according to the i-th original state machine.

When the complete string is processed, we have a vector of n values which are either "accepted" or "not accepted". There are $2^n$ possible outcomes. There are $2^{2^n}$ functions mapping each possible outcome to either "accepted" or "not accepted".

If we apply each of these functions, we get a new finite state machine defining a new language, one for each possible set operation on the n languages.

For two languages L and M, there are 16 possible set operations. Six are trivial, giving all strings, the empty set, L, M, the complement of L or the complement of M. The others are L or the complement of L intersected with M or the complement of M (four languages), the union of L or the complement of L with M or the complement of M (four languages), the strings that are either in L or M but not both, and the strings that are either both elements of L and M, or elements of neither. All these 16 languages are regular.

Out of three regular languages, we can produces 256 regular languages. Out of four regular languages, we can produce 65,536 regular languages, and out of five regular languages, about 4 billion.