2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Klaus Draeger May 1 '15 at 11:25
  • $\begingroup$ Nice exercise. Where does it come from? $\endgroup$ – J.-E. Pin May 1 '15 at 12:24
  • $\begingroup$ @J.-E.Pin A university assignment, have no idea if they make up the questions or get them from books etc (suspect the latter..). $\endgroup$ – Cauthon May 1 '15 at 12:34
1
$\begingroup$

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

  • $r_1 = \delta_1(q_1,a)$ and $r_2 = \delta_2(q_2,b)$ for some $b$, or
  • $r_2 = \delta_2(q_2,a)$ and $r_1 = \delta_1(q_1,b)$ for some $b$.
$\endgroup$
  • $\begingroup$ Thanks @Klaus, I think I got it. For each transition in the $NFA$, its set of possible states contains all combinations of $<r_1,r_2>$ that fit the criteria that you mentioned. That way there will always be a "path" that recognizes the correct words. Correct? Thanks for your help! $\endgroup$ – Cauthon May 1 '15 at 12:16
  • $\begingroup$ Yes, that is the idea. You're welcome! $\endgroup$ – Klaus Draeger May 1 '15 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.