Union of regular languages

Let L₁, L₂ be two regular languages. We will prove that their union L = L₁ ∪ L₂ is also a regular language.

Construction using a deterministic automaton

The idea

We have two regular languages L₁ and L₂ and we want to prove that their union L₁ ∪ L₂ is again a regular language. Since L₁ and L₂ are regular languages, there are finite automata A₁ and A₂ that accept the languages L₁ and L₂, so L(A₁) = L₁ and L(A₂) = L₂. We will now construct a finite automaton A that accepts the language L₁ ∪ L₂, which proves that the language L₁ ∪ L₂ is regular.

How do we do that? We have the finite automata A₁ and A₂, which accept the individual languages. We can say that a string w belongs to the language L₁ ∪ L₂ if and only if at least one of the automata A₁ or A₂ accepts it.

The automaton A could work as follows: for an input w it will simulate the run of the automaton A₁ on the input w. If A₁ accepts the string w, then A accepts the string w too. If A₁ rejects the string w, then A tries to simulate the run of A₂ on the input w. If A₂ accepts the string w, then A accepts the string w as well. Otherwise it rejects.

What remains is to formalise what it means for the automaton A to “simulate” the run of another automaton.

Formalisation

We have two regular languages L₁ and L₂, which are accepted by the finite automata

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

We construct a finite automaton A = ⟨Q, Σ, δ, q, F⟩ that accepts the language L = L₁ ∪ L₂. We will use the idea of simulating the two automata A₁, A₂. Imagine that the input is the string w = w₁w₂… w_n and that we simulate the runs of the automata A₁ and A₂ on the string w at the same time. The initial configuration of the automaton A₁ is ⟨q₁, w₁w₂… w_n⟩ and the initial configuration of A₂ is ⟨q₂, w₁w₂… w_n⟩. In each automaton we now perform one computation step, which takes us to the configurations ⟨δ₁(q₁, w₁), w₂… w_n⟩ and ⟨δ₂(q₂, w₁), w₂… w_n⟩.

We can see that these configurations differ only in the first component; the second one, the unread part of the string, is always the same. So during the simulation we do not need to keep two configurations of two automata; one configuration of the form ⟨⟨q_i, q_j⟩, w_l… w_n⟩ is enough, where q_i ∈ Q₁ and q_j ∈ Q₂. In other words, the automaton A we are constructing will have the initial configuration ⟨⟨q₁, q₂⟩, w⟩. The first part of the pair ⟨q₁, q₂⟩ is the state the automaton A₁ is currently in, and the second component is the current state of the automaton A₂.

So we can write that the automaton A will have a set of states equal to Q = Q₁ × Q₂. It will be the Cartesian product of the states of the two previous automata. The idea that follows is that the automaton A will have the start state ⟨q₁, q₂⟩, and if the automaton A₁ moves to the state q_i on the symbol w₁ and the automaton A₂ moves to the state q_j on the symbol w₁, then the automaton A moves to the state ⟨q_i, q_j⟩ on the symbol w₁.

We write the transition function δ like this (here we already assume that we are currently in the states q_i and q_j):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

All that remains is a few details. For the alphabet, Σ= Σ₁ ∪ Σ₂. The start state is q = ⟨q₁, q₂⟩. And the accepting states are all pairs ⟨q_i, q_j⟩ such that either q_i ∈ F₁ or q_j ∈ F₂.

Illustration of the construction

Let us take two automata. The first is the automaton A₁, which accepts all strings (including the empty string) in which zeros and ones alternate, that is, strings of the form 01, 0101, 010101, …

The other automaton A₂ accepts strings that contain at least one zero:

The union of these languages consists of the strings that either contain a zero or have the form 01, 0101, … Now we construct a finite automaton A = ⟨Q, Σ, δ, q, F⟩ that accepts exactly this union. First we show what the states of this new automaton A will look like. It will be the Cartesian product of the states of the first and second automaton:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

These are the six states of the automaton A that accepts the union L(A₁) ∪ L(A₂). In a diagram they would look like this:

Do not be put off by the states being made up of pairs of states; this is just to help us keep track of what is going on in the automaton. The states could just as well be called q₀, …, q₅ as usual. The accepting states are those that contain either the state q₀ or p₁, which are the accepting states of the original automata. The start state is ⟨q₀, p₀⟩.

Now we have to find all the transitions. We write down a table like this:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

And we fill in the table step by step. First we find where the transition from the state ⟨q₀, p₀⟩ leads on the input 0. We find where the transition from the state q₀ on the input 0 leads in the automaton A₁: it leads to the state q₁. In the automaton A₂ the transition from p₀ on zero leads to the state p₁. So we write ⟨q₁, p₁⟩ in the table:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

On the input 1 we get: for the automaton A₁ we have δ₁(q₀, 1) = q₂ and for the automaton A₂ we have δ₂(p₀, 1) = p₀. So we get the state ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

We fill in the rest of the table:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

And from this table we only need to draw the rest of the diagram.

We can check that the automaton works as it should. Let us try the string 0100. The automaton goes through the states

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Since the state ⟨q₂, p₁⟩ is an accepting state, the automaton A accepts the string 0100. How would it turn out if we tried to get the automata A₁ and A₂ to accept the string 0100? The automaton A₁ would go through these states:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

The automaton ended in the state q₂, which is not accepting, so the automaton A₁ would not accept this string. What about the automaton A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

The state p₁ is accepting, so the automaton A₂ would accept the string 0100. Notice that the automata A₁ and A₂ ended in the states q₂ and p₁, which agrees with the automaton A ending in the state ⟨q₂, p₁⟩.

Construction using a non-deterministic automaton

Example

We can also prove that the set of regular languages is closed under union by constructing a non-deterministic automaton, which will be much simpler.

So we have two regular languages L₁, L₂ and we want to prove that their union L = L₁ ∪ L₂ is also a regular language. Since L₁, L₂ are regular languages, there must be automata A₁, A₂ that accept these languages. That is, L(A₁) = L₁ and L(A₂) = L₂. Using these automata we construct an automaton A that accepts the language L, that is, L(A) = L.

Suppose that the finite automata A₁ and A₂ look like this:

and

We would construct an automaton that accepts the union of the two languages by creating a new start state and adding two epsilon transitions from it to the original start states. That is all. The automaton would look like this:

Formalisation

We have two automata A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ and A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. We construct an automaton A = ⟨Q, Σ, δ, q₀, F⟩ that accepts the union of the languages accepted by the previous automata, that is, L(A) = L(A₁) ∪ L(A₂). Here

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

And we define the transition function δ like this:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & if & q \in Q_{1} \\ δ_{2} (q, a) & if & q \in Q_{2} \\ {q_{1}, q_{2}} & if & q = q_{0} \land a = ε \\ \emptyset & if & q = q_{0} \land a \neq ε \end{cases}$

Sources

Chapters: Closure of regular languages, Union of regular languages, Intersection of regular languages, Difference of regular languages, Complement of a regular language, Concatenation of regular languages, Kleene closure of a regular language

« Previous: Closure properties of regular languages

Next: Intersection of regular languages »