The solution you give for $Mix_1$ doesn't seem quite right - consider the simple case $\Sigma=\{a\}$ and $L_1=L_2=\{\epsilon\}$, where $\epsilon$ is the empty word; obviously in this case, $Mix_1(L_1,L_2)$ should also be $\{\epsilon\}$. The minimal DFA for this language is $(\{q_0,q_1\},\Sigma,\delta,q_0,\{q_0\})$ with $\delta(q_0,a)=\delta(q_1,a)=q_1$. Your construction for $Mix_1$ gives an NFA with set of states $\{q_{0,1},q_{0,2},q_{1,1},q_{1,2}\}$, where $q_{0,1},q_{0,2}$ are both initial and accepting, with set of transitions $\{(q_{i,j},a,q_{1,j})\ |\ i\in\{0,1\},j\in\{1,2\}\}\cup\{(q_{i,1},a,q_{j,2}),(q_{i,2},a,q_{j,1})\ |\ i,j\in\{0,1\}\}$; this will accept all $w\in\Sigma^*$.

In order to solve this problem, both for $Mix_1$ and $Mix_2$, the automaton you want needs to do the following:

• keep track of the state of a DFA $A_1$ for $L_1$ while parsing one subset of the letters in the input,
• keep track of the state of a DFA $A_2$ for $L_2$ while parsing the remaining letters in the input,
• alternate between progressing in $A_1$ and $A_2$,
• accept when the last step was in $A_2$ and both $A_1,A_2$ are in an accepting state.

The only difference between $Mix_1$ and $Mix_2$ in this regard is when to alternate (for $Mix_1$: after each letter, for $Mix_2$: whenever you want).

The solution you give for $Mix_1$ doesn't seem quite right - consider the simple case $\Sigma=\{a\}$ and $L_1=L_2=\{\epsilon\}$, where $\epsilon$ is the empty word; obviously in this case, $Mix_1(L_1,L_2)$ should also be $\{\epsilon\}$. The minimal DFA for this language is $(\{q_0,q_1\},\Sigma,\delta,q_0,\{q_0\})$ with $\delta(q_0,a)=\delta(q_1,a)=q_1$. Your construction for $Mix_1$ gives an NFA with set of states $\{q_{0,1},q_{0,2},q_{1,1},q_{1,2}\}$, where $q_{0,1},q_{0,2}$ are both initial and accepting, with set of transitions $\{(q_{i,j},a,q_{1,j})\ |\ i\in\{0,1\},j\in\{1,2\}\}\cup\{(q_{i,1},a,q_{j,2}),(q_{i,2},a,q_{j,1})\ |\ i,j\in\{0,1\}\}$; this will accept all $w\in\Sigma^*$.

In order to solve this problem, both for $Mix_1$ and $Mix_2$, the automaton you want needs to do the following:

• keep track of the state of a DFA $A_1$ for $L_1$ while parsing one subset of the letters in the input,
• keep track of the state of a DFA $A_2$ for $L_2$ while parsing the remaining letters in the input,
• alternate between progressing in $A_1$ and $A_2$,
• accept when the last step was in $A_2$ and both $A_1,A_2$ are in an accepting state.

The only difference between $Mix_1$ and $Mix_2$ in this regard is when to alternate (for $Mix_1$: after each letter, for $Mix_2$: whenever you want).

In order to keep track of the necessary information, the states should be of the form $(q_1,q_2,i)\in Q_1\times Q_2\times\{1,2\}$, where $q_j$ represents the current state of $A_j (j=1,2)$, and $i$ indicates in which automaton we will next progress. The initial state is $(q_{01},q_{02},1)$, representing the fact that each $A_j$ is in its initial state $q_{0j}$ and we want to first progress in $A_1$. The accepting states are those $(q_1,q_2,1)$ with $q_1\in F_1$ and $q_2\in F_2$, i.e. both $A_j$ accepting.

This leaves the transition relation. For $Mix_1$ this involves taking one step in component $i$ and then toggling $i$ (this is also the reason for requiring $i=1$ in the accepting states, since the last step should be in $A_2$). For $Mix_2$, you can either toggle $i$ or take a step in component $i$ (note that this given an NFA, i.e. you still need to determinize).