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.
For any regular languages and , language is regular.
Since and are regular, there exist NFAs that recognize and .
In the following, we shall use to denote
Let be a string from . Without loss of generality assume .
Since accepts , there exist such that
We can therefore substitute for and rewrite the above path as
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.
- Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (See . Theorem 1.22, section 1.2, pg. 59.)