Theorem T2. The union of two regular languages is a regular language.

Proof. Let $L_1$ and $L_2$ be any regular languages, on alphabets ${\Sigma }_1$ and ${\Sigma }_2$ respectively. By exercise 5 of exercise set #1, $L_1$ and $L_2$ are both regular languages on the alphabet ${\Sigma }_1\cup {\Sigma }_2$; hence, by D6, there must be a finite automaton on ${\Sigma }_1\cup {\Sigma }_2$ that accepts exactly the members of $L_1$-say, one with states $Q_1=\{q_{10},\dots ,q_{1n}\}$, initial state $q_{10}$, final states $F_1$, and transition functon ${\delta }_1$-and a finite automaton ${\Sigma }_1\cup {\Sigma }_2$ that accepts exactly the members of $L_2$-say, one with states $Q_2=\{q_{20},\dots ,q_{2m}\}$, initial state $q_{20}$, final states $F_2$, and transition function ${\delta }_2$. We assume, without loss of generality, that $Q_1\cap Q_2=\varnothing$. (If the two automata somehow share states, the common states can be replaced with distinct but functionally equivalent states so as to ensure that this condition is met; proving that this is always possible involves a simple double induction, on the number of states to be replaced and on the length of input strings.)

Construct a new nondeterministic finite automaton on the alphabet ${\Sigma }_1\cup {\Sigma }_2$ with states

${\displaystyle Q_{\cup }=Q_1\cup Q_2\cup \{q_{\cup }\}}$

(where $q_{\cup }$ is the new initial state), final states

${\displaystyle F_{\cup }=\{\begin{array}{cc}\hfill F_1\cup F_2\cup \{q_{\cup }\},\hfill & \hfill \mathrm{if}{q}_{10}\in F_1\mathrm{or}{q}_{20}\in F_2;\hfill \\ \multicolumn{1}{c}{F_1\cup F_2}& \hfill \mathrm{otherwise},\hfill \end{array}}$

and transition function ${\delta }_{\cup }$ defined by

${\displaystyle {\delta }_{\cup }(q,a)=\{\begin{array}{cc}\hfill \{{\delta }_1(q,a)\},\hfill & \hfill \mathrm{if}q\in Q_1;\hfill \\ \multicolumn{1}{c}{\{{\delta }_2(q,a)\},}& \hfill \mathrm{if}q\in Q_2;\hfill \\ \multicolumn{1}{c}{\{{\delta }_1(q_{10},a),{\delta }_2(q_{20},a)\},}& \hfill \mathrm{if}q=q_{\cup }.\hfill \end{array}}$

We shall show that this nondeterministic finite automaton accepts $L_1\cup L_2$. First of all, there is an easy special case: The nondeterministic finite automaton accepts the null string, $\epsilon$, iff it is a member of $L_1\cup L_2$. For $\epsilon$ is accepted iff the initial state $q_{\cup }\in F_{\cup }$, which by the definition of $F_{\cup }$ is true iff the initial state of one of the finite automata is a member of the set of final states for that automaton, which in turn is true iff $\epsilon$ is accepted by that automaton and hence in either $L_1$ or $L_2$.

For longer strings, we need an inductive argument, this time with a base step dealing with strings of length 1; treating such strings in a separate case seems to be the easiest way of dealing with the exceptional transition from the initial state of the nondeterministic finite automaton. The inductive proposition must be formulated with some care, so that it will be general enough: We show that for any non-null string $x\in ({\Sigma }_1\cup {\Sigma }_2{)}^{*}$, the result set $\widehat{{\delta }_{\cup }}(q_{\cup },x)$ on $x$ in the nondeterministic finite automaton will have as its sole members the result states $\widehat{{\delta }_1}(q_{10},x)$ and $\widehat{{\delta }_2}(q_{20},x)$ of the two finite automata on $x$.

Base step. If $\left|x\right|$ is 1, the proposition follows directly from the third clause of the definition of ${\delta }_{\cup }$, by D4(b) and D8(b).

Induction step. Suppose $\left|x\right|=k+1$, for some $k\ge 1$. Then $x=\mathrm{wa}$, where $w$ is a string of length $k$ on ${\Sigma }_1\cup {\Sigma }_2$ and $a\in {\Sigma }_1\cup {\Sigma }_2$. Now,

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{\widehat{{\delta }_{\cup }}(q_{\cup },\mathrm{wa})}& =\bigcup _{q\in \widehat{{\delta }_{\cup }}(q_{\cup },w)}{\delta }_{\cup }(q,a)\hfill & \text{(by D8(b))}\hfill \\ \multicolumn{1}{c}{}& ={\delta }_{\cup }(\widehat{{\delta }_1}(q_{10},w),a)\cup {\delta }_{\cup }(\widehat{{\delta }_2}(q_{20},w),a)\hfill & \hfill \\ \multicolumn{1}{c}{}& \hfill & \text{(by the hypothesis of induction)}\hfill \\ \multicolumn{1}{c}{}& =\{{\delta }_1(\widehat{{\delta }_1}(q_{10},w),a),{\delta }_2(\widehat{{\delta }_2}(q_{20},w),a)\}\hfill & \hfill \\ \multicolumn{1}{c}{}& \hfill & \text{(by the definition of}{\delta }_{\cup })\hfill \\ \multicolumn{1}{c}{}& =\{\widehat{{\delta }_1}(q_{10},\mathrm{wa}),\widehat{{\delta }_2}(q_{20},\mathrm{wa})\}\hfill & \text{(by D4(b))}\hfill \end{array}}$

since $\widehat{{\delta }_1}(q_{10},w)\in Q_1$ and $\widehat{{\delta }_2}(q_{20},w)\in Q_2$. This completes the induction.

Now, first let $x$ be any member of $L_1$ (other than $\epsilon$). The result state of the finite automaton for $L_1$ on $x$ is a final state of that finite automaton, by D5, and hence also a final state of the nondeterministic finite automaton, by the definition of $F_{\cup }$. Since this result state is in the result set of the nondeterministic finite automaton on $x$, the nondeterministic finite automaton accepts $x$, by D9. Similarly, if $x\in L_2$, $x\ne \epsilon$, then the nondeterministic finite automaton accepts $x$.

Conversely, let $x$ by any member of $({\Sigma }_1\cup {\Sigma }_2{)}^{*}-\epsilon$ that is accepted by the nondeterministic finite automaton. By D9, the result set of the nondeterministic finite automaton on $x$ has as a member some final state $q_f$ of the nondeterministic finite automaton. This $q_f$ cannot be $q_{\cup }$, since it is reached by a non-empty sequence of transitions, and there are no transitions into $q_{\cup }$. It must therefore be a member of $F_1$ or of $F_2$. Suppose it is a member of $F_1$. Since $F_1\subseteq Q_1$, $q_f\in Q_1$. Hence, by the inductive argument, $q_f=\widehat{{\delta }_1}(q_{10},x)$, since $\widehat{{\delta }_2}(q_{20},x)\notin Q_1$. Therefore, the finite automaton for $L_1$ accepts $x$, which is to say that $x\in L_1$. Similarly, if $q_f\in F_2$, then $x\in L_2$.

Thus the nondeterministic finite automaton accepts $x$ iff either $x\in L_1$ or $x\in L_2$, that is, iff $x\in L_1\cup L_2$. This has now been shown to hold both for $x=\epsilon$ and for $x\ne \epsilon$. Hence, by D10, the nondeterministic finite automaton accepts $L_1\cup L_2$. Hence, by theorem T1, $L_1\cup L_2$ is regular. $•$

---

File translated from T_EX by T_TM, version 3.61.
On 9 Jul 2004, 10:20.