2.3k 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

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)

States a b
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
Is there any difference in the product automaton of Z x Y and Y x Z ?
Does ZxY means concatenation of automata?
No, it is intersection
It is product rt?
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.
okay.. Let me check..
@Arjun sir ,  this is concatenation operation and you applied cross product method.. So, can we apply cross product method on concatenation operation also ??

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

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

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

@Arjun Sir, so can we consider that as a misprint or a typing error?
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 ??????

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

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!
here they have  asked cross product , not intersection machine .
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.