edited by
14,461 views
67 votes
67 votes

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

  1. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{S} & \text{R} \\\hline  \text{Q} & \text{R} & \text{S} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{Q} & \text{P}\\\hline \end{array}$
  2. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{S} & \text{Q} \\\hline  \text{Q} & \text{R} & \text{S} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{P} & \text{Q}\\\hline \end{array}$
  3. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{Q} & \text{S} \\\hline  \text{Q} & \text{R} & \text{S} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{Q} & \text{P}\\\hline \end{array}$
  4. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{S} & \text{Q} \\\hline  \text{Q} & \text{S} & \text{R} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{Q} & \text{P}\\\hline \end{array}$
edited by

4 Answers

Best answer
63 votes
63 votes

$$\begin{array}{|l|l|l|l|}\hline \textbf{}  &  \textbf{States} & \textbf{a} & \textbf{b} \\\hline  \text{$\rightarrow$}  &  \textbf{11(P)} & 12 & 22 \\\hline   \text{}  &  \textbf{12(S)} & 11 & 21 \\\hline \text{}  &  \textbf{21(Q)} & 22 & 12 \\\hline \textbf{(F)}  &  \textbf{22(R)} & 21 & 11 \\\hline \end{array}$$

$11$ is $P$ and $22$ is $R$ in choice. So, the answer should be (A) but in the row for $S$, it should be $P$ and $Q$ and not $Q$ and $P$. 

edited by
28 votes
28 votes

Correct answer is option A. 

New final state where finals of both FA's are together.

edited by
11 votes
11 votes

Another alternative to get the answer can be :

Y represents strings with odd number of b {Nb(W) mod 2 = 1)} and Z represents odd number of strings {|W| mod 2 =1}

If we take the product automata ZxY i.e. Odd number of String and Odd number of b in string which is nothing but "Strings with Odd no of b and Even no of a" Draw the mod m/c for this and pick the correct option i.e. A

7 votes
7 votes
Answer:

Related questions

34 votes
34 votes
2 answers
2