# Two DFA to one NFA.

Let assume that I have given DFA $D$ which recognize language $L$. Now I would like create the DFA/NFA which recognize the language $L'$. $$L' = \{ w \in L : |w| = 2k, k \ge 0 \}$$ In words, $L'$ contains words form $L$ of even length. So I imagine NFA like:

And now, the "green" automata recognize if length of word is even. If yes it take a accepted state ( Q1). And the second condition is such that DFA $D$ recognize if the word is acceptable by $L$. If yes, the NFA take state $Q4$

And now: $e$ means a empty word.

blue arrows are connected with the acceptable state in D with my state Q4.

So my NFA recognize word iff the machine has a Q1 AND Q4 state. I don't know how to get AND relation.

As you observed, you get an OR relation by doing a disjoint sum, as in your diagram. To get an AND relation, you must take the product of the two automata. The product of $A$ and $B$ has states that are pairs of states, one from $A$ and one from $B$, so that it tracks the states of $A$ and $B$ together. Then it can accept if it is in a state $\langle a,b\rangle$ where $A$ would accept in state $a$ AND if $B$ would accept in state $b$.
• Usually you use the M-N theorem to prove that a certain language is, or is not, regular. So look in your book for exercises of the type "Show that language $L$ is regular" or "Is language $L$ regular?" and then try to apply the Myhill-Nerode theorem.