The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 votes

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


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


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


asked in Theory of Computation by Veteran (59.4k points)
edited by | 2.6k views
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.


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

4 Answers

+28 votes
Best answer


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

answered by Veteran (339k points)
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 ??????
+6 votes

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

answered by (443 points)
+5 votes
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!
answered by Boss (17k points)
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,781 questions
41,758 answers
41,400 users