1

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$?

TheNotMe
  • 4,841

2 Answers2

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.

enter image description here

I. J. Kennedy
  • 4,048
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.

apt1002
  • 2,033
  • What does the sign $+$ mean in $Q_1 x Q_2 + Q_2 x Q_1$? – TheNotMe Nov 14 '13 at 23:23
  • It means the disjoint sum. An element of $A+B$ is either an element of $A$ or an element of $B$ but not both. If A and B intersect, then we must magic up some injections to avoid a collision. – apt1002 Nov 14 '13 at 23:35
  • Ugh, looks like I might have misread your question. I thought you meant $\theta_1\ldots\theta_n$ is a single word of $L_1$. Is that what you mean? – apt1002 Nov 14 '13 at 23:40
  • It is, your understanding is fine. Thanks alot! – TheNotMe Nov 14 '13 at 23:51