Let $L_1, L_2$ be regular languages. You can proof with a product automaton that $L_1\cup L_2$ is also regular. But you can also construct a NFA. Since $L_1, L_2$ are regular, they also have an NFA representation $M_1, M_2$. You can create a NFA with a start state $q_0$ with one edge each to the start states of $M_1,M_2$ with an epsilon transition.
So I wonder what is the difference, advantages and disadvantages?
Thx!
Both constructions work. The advantages of using NFAs is that they allow easier constructions, especially for languages that can be naturally specified using existential quantifiers. So if we only care about proving whether some language is regular, then easy design wins. As you've wrote, putting two automata next to each other and guessing which automaton to run on the input word is a straight-forward construction compared to the product construction, and indeed, in this case we want to check whether there exists an automaton (one of the two automata that we started with) that accepts the input word: the construction simply guesses which automaton to run on the input.
Another classical example is closure of regular languages under concatenation, where we want to check whether there exists a partition of the input word into two words such that the first word is accepted by one automaton, and the second word is accepted by the other automaton. Here, we guess while reading the input word when we branch and run the second automaton on the suffix to be read. Also, many more examples exist where NFAs allow for conceptually easier constructions. Its just that existential properties and NFAs work well with each other due to the existential semantics of nondeterminism: a nondeterministic automaton accepts an input if there exists a run of it on the input.
The disadvantages of such constructions is that while they are conceptually simple, they do not necessarily preserve determinism. So while nondeterminism allows more elegant designs, we prefer constructions that end up with deterministic automata (preferable small ones) since decision procedures about deterministic automata are considebraly easier than decision procedures about nondeterministic automata: language containment, minimization, etc, are all in PTIME for deterministic automata, yet PSPACE-complete for nondeterministic ones. In this sense, the product construction is better as it preserves determinism (the product of deterministic automata is deterministic) and results in an automaton of quadratic size (which is at most polynomial in the two automata that we started with -- good!).
