3.7k views

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

Y
$a$ $b$
$\rightarrow$ $1$ $1$ $2$
$2 (F)$ $2$ $1$
Z
$a$ $b$
$\rightarrow$ $1$ $2$ $2$
$2 (F)$ $1$ $1$

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

1.  $a$ $b$ $\rightarrow$ $P$ $S$ $R$ $Q$ $R$ $S$ $R(F)$ $Q$ $P$ $S$ $Q$ $P$
2.  $a$ $b$ $\rightarrow$ $P$ $S$ $Q$ $Q$ $R$ $S$ $R(F)$ $Q$ $P$ $S$ $P$ $Q$
3.  $a$ $b$ $\rightarrow$ $P$ $Q$ $S$ $Q$ $R$ $S$ $R(F)$ $Q$ $P$ $S$ $Q$ $P$
4.  $a$ $b$ $\rightarrow$ $P$ $S$ $Q$ $Q$ $S$ $R$ $R(F)$ $Q$ $P$ $S$ $Q$ $P$
edited | 3.7k views
+12
I am getting answer as option A. but in last row instead of S -> Q | P I am getting S-> P | Q.
+1
You are correct. That must be a printing mistake.
+3

..

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

States $\mathbf{a}$ $\mathbf{b}$
$\rightarrow$ 11 (P) $12$ $22$
12 (S) $11$ $21$
21 (Q) $22$ $12$
(F) 22 (R) $21$ $11$

So, $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
+2
Is there any difference in the product automaton of Z x Y and Y x Z ?
+1
Does ZxY means concatenation of automata?
+10
No, it is intersection
0
It is product rt?
+10
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
okay.. Let me check..
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 ?

+2
In the end, try to map whichever is matching the given choices. No, other rule.
0

Arjun sir, I guess you have found Y x Z. Is Y x Z and Z x Y the same ?

0
@Arjun Sir, so can we consider that as a misprint or a typing error?
0
sir can you plz explain difference b/w Y x Z and Z x Y bcoz i think it is Y x Z. not Z x Y ??????
0
@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.
0

{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.

0
Is there any good source to read union,intersection,concatenation and cross product of automaton in detail?
0

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

0
I got the same. ( Answer will remain same i.e. option A for Z×Y and Y×Z)
0

@Harshada-Which table you got? Mine or That given in the answer by Arjun sir?

0

Same as your table @Ayush ! (Z×Y)

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

0
Yes this way we can check the correct option.
The simplest way to answer this question is, both the DFA accept single 'b', intersection of both DFA should allow to accept single 'b' by new machine
in option (A) only, single b can be accepted!
0
here they have  asked cross product , not intersection machine .
+2
Cross product means, when both are true. It is intersection. See proof for regular languages Intersection.  The proof is done using cross product. Both will run in parallel. When both will reach final state, it is accepted.

### Correct answer is option A.

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

edited

1
2