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

I am getting answer as option A. but in last row instead of S -> Q | P I am getting S-> P | Q.

---

You are correct. That must be a printing mistake.

---

thanks

---

ans will be option B bcz in last two row entries are (Q,P) and (P,Q)

---

For those finding it difficult to map the states, in ZxY:

Start State → b→ Final State & Final State→ b→ Start State. This can be used to eliminate the options B, C, D. But although A satisfies first three transitions, last one wrongly given in the option.

---

https://youtu.be/CWei4YjTj90?si=Nd2VdJK-cAoxHfzf

refer this for cross product of DFA

---

Then there should be 3 final states na?

---

Correct Answer

---

"Construct the product automaton of Z x Y"

but doesn’t specify the operation (union, intersection, etc.), by default, in theory of computation, product automaton usually refers to  intersection.

---

This question has mistake in Option A , you will get answer like Pranay Answer 

https://gateoverflow.in/462/gate-cse-2008-question-49?show=473307#c473307

---

https://www.geeksforgeeks.org/theory-of-computation/cross-product-operation-in-dfa/

---

@arbpass can you provide source where it is mentioned?

---

ambiguous question in my opinion if you ask me

---

it would be same Y x Z right?

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.