Operation $random$ is defined on two words with equal length in the following way:
$\forall w_1,w_2 \in \Sigma^* s.t. |w_1|=|w_2|=n, w_1=a_1a_2…a_n, w_2=b_1b_2…b_n:$
$Random(w_1,w_2) = \{\sigma_1\sigma_2…\sigma_n|\forall i, 1\leq i \leq n, \sigma_i \in \{a_i,b_i\}\}$
Expanding this operation for all languages $L_1,L_2$ over $\Sigma^*$, we define:
$Random(L_1,L_2) = \{Random(w_1,w_2) | w_1 \in L_1, w_2 \in L_2\}$
Prove that if $L_1,L_2$ are regular, then $Random(L_1,L_2)$ is regular.
I tried coming up with an $NFA$ that will recognize the new language, but I get stuck with defining the transition function. Ideally I'd like to define it to work by: "For each letter $\sigma_i$, choose the transition function non-deterministically from one of the two $DFA$s of $L_1,L_2$." But that's not correct since I need to know if the letter $\sigma_i$ exists in position $i$ in a word from $L_1,L_2$, I don't really care about their states (I think).
I'm also not sure how to handle the fact that it must also check that the word was chosen randomly from two words of equal length.
Any advice of how to tackle this would be appreciated.
Best Answer
Your idea goes in the right direction - you just need to also keep track of the fact that you essentially "skipped" an input in the non-chosen automaton. In a nutshell, what you want is a variant product construction: Let the original automata be $A_i=(Q_i,q_i^0,F_i,\delta_i)$ for $i=1,2$.
Then your NFA has set of states $Q_1\times Q_2$, with initial state $(q_1^0,q_2^0)$ and set of accepting states $F_1\times F_2$, and a transition $((q_1,q_2),a,(r_1,r_2))$ iff either