Union of two Non deterministic Finite automata

Question

How to perform union of two NFAs. This question is from Peter Linz's book.

Find an NFA with four states for $L=\{ a^n \ | \ n \geq 0 \} \cup \{b^n a \ | \ n \geq 1\}$.

Now Considering the first part as $L_1$ and second part as $L_2$ I am enclosing the solution.
The problem is I can't make out how strings like $\{\epsilon,a,aa,aaa,\dots\}$ are getting accepted in the final NFA.

Please help me to interpret the solution.

Answer 1

To take the union of two NFAs, you just need to add an initial state with an $\epsilon$-transition to each of the initial states of the original NFAs. So if your $L_1$ and $L_2$ are

you get

That doesn't fully satisfy the requirements of the exercise, because you're supposed to have only 4 states. But because $L$ and $C$ have exactly the same incoming edges (i.e. none) and the same termination value (i.e. not accepting) we can merge them, eliminating the epsilon transition, to get

In this particular case, it's also possible to eliminate the remaining epsilon transition:

To make it a proper DFA, however, would require adding a sink state for the edges which are suppressed in the NFA:

Answer 2

It's easier to answer it for the general case. Suppose you have $k$ NFAs (right, not necessarily DFA; of course, a DFA is a special case of an NFA), $N_1$ for $L_1$, $N_2$ for $L_2$, ... $N_k$ for $L_k$. Just pose all automata together next to each other (even if they have states with the same names, copy everything).

Formally, Define an NFA N such that

• $Q = \bigcup_{1 \le i \le k} Q_i$

• $q_0 = {q_0}_i (\forall 1 \le i \le k)$ (Merge all the start states.)

• $F = \bigcup_{1 \le i \le k} F_i$

• $\delta(q) = \delta_i(q)$ where $i$ is the NFA to which this state ($q$) belongs.

  Note that by construction the destination states are also in $Q_i$.

• $\Sigma = \bigcup_{1 \le i \le k} \Sigma_i$

Effectively, each run is done inside one NFA. so if there is an accepting run, starting from $q \in Q_0$ and ending in $q' \in F$, then there must exists $i$ s.t. $q \in Q_i$, $q' \in F_i$, and all transition were performed according to $\delta_i$ using $\Sigma_i$, so $N_i$ accepts, so $w \in L_i$. So $L(N)$ is included in the union of $L_i$s.

Conversely, if $w$ in the union, then there exists $i$ s.t. $w$ in $L_i$ and there exists an accepting run in $N_i$, then the very same run exists also in $N$, so the union in $L(N)$. So $L(N) = \bigcup_{1 \le i \le k} L_i$