I am reading a book called Introduction of the Theory of Computation. In the book, the author tries to proof $A_1 \cup A_2$ is regular if $A_1$ and $A_2$ are regular.
He is using Proof by Construction. I understood that we have to construct $M$ from $M_1$ which recognizes $A_1$ and $M_2$ which recognizes $A_2$ in order to proof that union of two regular languages also gives you regular language.
But I am not understanding this statement, "If $M_1$ has $k_1$ states and $M_2$ has $k_2$ states, the number of pairs of states, one from $M_1$ and the other $M_2$, is the product $k_1 \times k_2$."
Shouldn't be the number of states for $M$ be the addition of $M_1$ and $M_2$ and initial state for $M$?
For Example, if $M_1$ has 3 states and $M_2$ has 3 states, then $M$ should have $M_1$'s states and $M_2$'s states and one additional state for the initial state for $M$. In total 7 states. But the book is saying, we should have $3 \times 3 = 9$ states.
I know I am stupid and wrong. But can you explain it as you are explaining to a 5-year old kid?
The book is, presumably, building a deterministic finite automaton from two deterministic finite automata. You, however, are building a non-deterministic automaton: from your new initial state, you have $\varepsilon$-transitions to the initial states of $M_1$ and $M_2$.