GATE CSE 2008 | Question: 49

Question

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

Comments

it would be same Y x Z right?

---

if you are confused just change the state name  to 1' and 2' in one machine ...then also the answer is correct

---

Make Both FA and use product  autometa

Option A is correct

Answer 1

$$\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$. 

Comments

@Arjun sir, Could you plz clear that YxZ and ZxY are same or different?

---

 

---

@Pranay_VG 

Got the same answer

Answer 2

Correct answer is option A. 

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

Comments

I have the same question as above jeerujay :

When we do Z x Y then from Z → a (it goes to state 2), From Y → a (it goes to state 1), from 11 by reading a, it as to go 21, but your transition goes to 12 how?

let me know if I’m wrong.

---

how did you draw the transition diagram?

---

Approach is useful but but you have done opposite cross product!

Answer 3

Another alternative to get the answer can be :

Y represents strings with odd number of b {N_b(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

Comments

Yes this way we can check the correct option.

---

@aayushranjan01  is automata Z accepting the string aaa? If yes, option a is not accepting aaa.. 

Answer 4

Refer this pdf i think you will get all concepts related cross product

https://www.google.co.in/url?sa=t&source=web&rct=j&url=https://www.andrew.cmu.edu/user/ko/pdfs/lecture-3.pdf&ved=0ahUKEwjVofen6dnKAhUIbY4KHbzZALUQFggaMAA&usg=AFQjCNGzYD5ZB3il9wvu9ScUQ6vuX5u8Wg&sig2=XVbLlspxl22Zjd1yeew1Kg

Comments

@Mostafize Mondal

Bro you did Y X Z. But we have to perform

Z X Y.

But yeah we have to choose option A) ( last two rows are wrong-print mistake)

Answer 5

Simplest possible method is by eliminating options.
if we do cross product then it'll create new states. in Z initial state on b goes to 2 and initial stage of y on b goes to 2 in both qns 2 is final state. so in the final ZxY also it'll go to final state. final state of the answer is R and you can eliminate all options instantly here since except option a none of the other options are going to R (final state). thus Option A is correct answer.

Check if this is correct for this qn @Arjun sir.