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.


1 Answer 1


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

  • $\begingroup$ 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? $\endgroup$
    – WindBreeze
    Commented May 31, 2020 at 15:51
  • $\begingroup$ Can you also explain why we do Q_A x Q_b ?(why the cross product in this case?) $\endgroup$
    – WindBreeze
    Commented May 31, 2020 at 15:52
  • $\begingroup$ 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) $\endgroup$
    – nir shahar
    Commented May 31, 2020 at 15:53
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Commented May 31, 2020 at 15:55
  • $\begingroup$ 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? $\endgroup$
    – WindBreeze
    Commented May 31, 2020 at 15:57

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