The Gateway to Computer Science Excellence

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

+43 votes

Best answer

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

+13

Yes. it is , but when we are marking New (F) where finals of both FA's are together, then it results in Intersection in terms of language.

0

@Arjun sir , this is concatenation operation and you applied cross product method.. So, can we apply cross product method on concatenation operation also ??

0

@Arjun SIR , How did you know that P is 11 ?

I took P(11) Q(12)R(21)S(22) . Will it make any difference ? Is there any restriction to choose the states ?

+1

@rajoramanoj Sir has actually shown it for YXZ but anyway YXZ & ZXY are actually same, only order of state differs, both are having exactly same dfa if you check.

+2

{1,1} = starting state =P (given)

{1,2} = Q / S

{2,1} = Q/S

{2,2}=Final state = R (given)

now correlate with options you will get your answer.

+3

@Arjun-Sir your table seems to be for $Y \times Z$. But question is for $Z \times Y$

I got below table

$Z \times Y$ | a | b |

11 | 21 | 22 |

12 | 22 | 21 |

21 | 11 | 12 |

22 | 12 | 11 |

Is this correct?

+13 votes

+9 votes

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

+6 votes

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

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

52,345 questions

60,468 answers

201,792 comments

95,271 users