Given below are two finite state automata (→ indicates the start state and F…

Concept

The product automaton for two DFAs (built to accept the intersection of their languages) has states that are ordered pairs (state of the first machine, state of the second machine). Its start state is the pair of the two start states; each transition moves both components at once, each using its own transition rule; and a pair is a final state only when BOTH components are individually final in their own machine.

Application

Apply this to Z x Y. Z flips its state on every input (state 1 goes to state 2 and vice-versa, on both a and b). Y stays at state 1 on a and moves to state 2 on b, and at state 2 it moves to state 2 on a and back to state 1 on b. Following the diagram’s own labelling, let P be the combined start pair, and let R be the pair where both components are simultaneously final (the only state that can be marked final).

1. From P (Z at its start, Y at its start): on a, Z moves to its final state while Y stays at its own start, so only one component is final — call this pair S. On b, Z moves to its final state and Y also moves to its own final state, so BOTH components are final — this must be R. So P: a → S, b → R.

2. From R (Z final, Y final): on a, Z flips back to its start while Y (which loops at its final state on a) stays final, so only Y is final — call this pair Q. On b, Z flips back to its start and Y also returns to its own start, so neither is final — this is P again. So R: a → Q, b → P.

3. From Q (Z at its start, Y at its final state): on a, Z moves to its final state and Y stays final, so both are final — R. On b, Z moves to its final state and Y returns to its own start, so only Z is final — S. So Q: a → R, b → S.

4. From S (Z at its final state, Y at its start): on a, Z flips back to its start and Y stays at its own start, so neither is final — P. On b, Z flips back to its start and Y moves to its own final state, so only Y is final — Q. So S: a → P, b → Q.

Cross-check

As an independent check, trace a couple of sample strings through the true product behaviour directly: reading just b from the start, Z and Y each reach their own final state, so b must be accepted; reading aab, both Z and Y are back at their own final state as well, so aab must also be accepted. Comparing this derivation with the four given tables: exactly one table reproduces every row derived above — P: a → S, b → R; Q: a → R, b → S; R (the final state): a → Q, b → P; and S: a → P, b → Q. Tracing b and aab through that table from P confirms both are accepted, matching the check above. The other three tables each depart from this pattern in at least one row (two send P to Q instead of the final state on b, and the remaining one sends P to Q instead of S on a, with further mismatches besides), so none of them can be Z x Y. The table matching every row above is therefore the correct representation of Z x Y.