GATEverse — GATE CSE previous year questions

Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state)

\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & \textbf{a} & \textbf{b} \\\hline \text{$\rightarrow$ $1$} & \text{1} & \text{2} \\\hline \text{$2 (F)$} & \text{2} & \text{1} \\\hline \end{array}} \qquad \overset{Z}{\begin{array}{|l|l|l|}\hline \text{} & \textbf{a} & \textbf{b} \\\hline \text{$\rightarrow$ $1$} & \text{2} & \text{2} \\\hline \text{$2 (F)$} & \text{1} & \text{1} \\\hline \end{array}}

Which of the following represents the product automaton $Z \times Y$ ?

(A)

\begin{array}{|l|l|l|} \hline & a & b \\ \hline \rightarrow P & S & R \\ \hline Q & R & S \\ \hline R(F) & Q & P \\ \hline S & Q & P \\ \hline \end{array}

(B)

\begin{array}{|l|l|l|} \hline & a & b \\ \hline \rightarrow P & S & Q \\ \hline Q & R & S \\ \hline R(F) & Q & P \\ \hline S & P & Q \\ \hline \end{array}

(C)

\begin{array}{|l|l|l|} \hline & a & b \\ \hline \rightarrow P & Q & S \\ \hline Q & R & S \\ \hline R(F) & Q & P \\ \hline S & Q & P \\ \hline \end{array}

(D)

\begin{array}{|l|l|l|} \hline & a & b \\ \hline \rightarrow P & S & Q \\ \hline Q & S & R \\ \hline R(F) & Q & P \\ \hline S & Q & P \\ \hline \end{array}