Union of two regular languages


In formal language theory, and in particular the theory of nondeterministic finite automata, it is known that the union of two regular languages is a regular language. This article provides a proof of that statement.

Theorem

For any regular languages and, language is regular.
Proof''
Since and are regular, there exist NFAs that recognize and.
Let

Construct
where
In the following, we shall use to denote
Let be a string from. Without loss of generality assume.
Let where
Since accepts, there exist such that
Since
We can therefore substitute for and rewrite the above path as
Furthermore,
and
The above path can be rewritten as
Therefore, accepts and the proof is complete.
Note: The idea drawn from this mathematical proof for constructing a machine to recognize is to create an initial state and connect it to the initial states of and using arrows.