# How to define an automata for zig zag concatenation? [duplicate]

I have two DFAs one for language A and one for language B. I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B. This is described by the following: {w: w = $$a_1 b_1$$...$$a_k b_k$$ and $$a_1...a_k \in A$$ and $$b_1 ... b_k \in B$$}. With $$1 \leq i \leq k$$ and $$a_i \in \Sigma$$ and $$b_i \in \Sigma$$

This automata should be described as a 5-tuple {Q, $$\Sigma$$,$$\delta$$,$$q_0$$,$$F$$}.

I simply do not know how I would go about defining the total function $$\delta$$.

This is what I tried:

$$Q = Q_A \cap Q_B$$ // We only want the words that contains both a and b

$$F = F_A \cap F_B$$ // The accepted states should contain both letter from a and from b.

$$q_0 = q_A$$ //because the word starts with a letter from a.

$$\Sigma$$ // in this problem we aren't interested in defining the alphabet we just leave the symbol as is in the 5-tuple.

let $$Q=Q_A\times Q_B\times \{1,2\}$$ (1 means A, 2 means B)

also define $$F=F_A\times F_B\times \{2\}$$ (we end with B)

and $$q_0=(q_A,q_B,1)$$ (we start with A)

with the delta function: $$\delta ((q_1,q_2, i),\sigma)= \begin{cases} (\delta(q_1,\sigma),q_2,2) &i=1 \\ (q_1, \delta(q_2,\sigma),1) &i=2 \end{cases}$$

The idea is to encode both A and B together, with some "index" telling us if we need to check A or B

• At first glance what does {1,2} (1-A, 2-B) mean exactly? Is this the index we give A and B? But why the subtraction of 1-A and 2-B? – WindBreeze May 31 at 15:51
• Can you also explain why we do Q_A x Q_b ?(why the cross product in this case?) – WindBreeze May 31 at 15:52
• This is a comment, explaining that "1" means we are checking A currently and "2" means we are checking B (i fixed it so it would look more like an explanation and not random subtruction) – nir shahar May 31 at 15:53
• The cross product is just so we would be able to save two states at one time. I recommend taking a look at the proof that regular languages are closed under intersection, since this uses a similar trick – nir shahar May 31 at 15:55
• Is it possible to visualize what is happening? I have trouble wrapping my head around about what the cross product of Q_a and Q_b with {1,2} mean. Do you mean (1,2) where we have kind of like a coordinate? – WindBreeze May 31 at 15:57