New automaton that runs two others step by step?

Question

If I have two automatons for two languages ($M_1, M_2, L_1,L_2$ respectively), what would be the procedure to mix them by defining a new automaton such that the new automaton would accept the words $\theta_1\sigma_1\theta_2\sigma_2...\theta_n\sigma_n $ where $\theta_1 ... \theta_n \in L_1 , \sigma_1 ... \sigma_n \in L_2 $? By making it run from $M_1$ to $M_2$ to $M_1$ again to $M_2$ again and finally to an accepting state of $M_1$?

Answer 1

You did not define what kind of automaton you want. I will use finite state automatons. Let $M_1$ have state set $Q_1$, symbol set $S_1$, initial state $i_1 \in Q_1$, transition function $t_1: Q_1×S_1 \mapsto Q_1$ and accepting states $A_1 \subseteq Q_1$. Similarly define the components of $M_2$.

We can construct the machine you want with:

• states $Q_1×Q_2 + Q_2×Q_1$,
• symbols $S_1 + S_2$,
• initial state $(i_1, i_2)$,
• transition function left as exercise, :-)
• accepting states $A_1×A_2$.

I hope you can finish it from here.

Answer 2

Assuming $M_1$ and $M_2$ are deterministic finite state machines, form a non-deterministic finite automaton with ε moves as shown below and then apply the powerset construction to get a deterministic one.