The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+32 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$?

  1. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{S} & \text{R} \\\hline  \text{Q} & \text{R} & \text{S} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{Q} & \text{P}\\\hline \end{array}$
  2. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{S} & \text{Q} \\\hline  \text{Q} & \text{R} & \text{S} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{P} & \text{Q}\\\hline \end{array}$
  3. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{Q} & \text{S} \\\hline  \text{Q} & \text{R} & \text{S} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{Q} & \text{P}\\\hline \end{array}$
  4. $\begin{array}{|l|l|}\hline \text{}  &  \text{a} & \text{b}  \\\hline \text{$\rightarrow$ $P$} & \text{S} & \text{Q} \\\hline  \text{Q} & \text{S} & \text{R} \\\hline  \text{R(F)} & \text{Q} & \text{P}\\\hline \text{S} & \text{Q} & \text{P}\\\hline \end{array}$
asked in Theory of Computation by Veteran (59.8k points)
edited by | 4k 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)

5 Answers

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

answered by Veteran (400k 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 ??????
@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.


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

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

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

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

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



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

+8 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 (471 points)
Yes this way we can check the correct option.
+8 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 (17.3k 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.
+5 votes

Correct answer is option A. 

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

answered by Active (1.7k points)
edited by
+3 votes
answered by (245 points)

Related questions

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
49,408 questions
53,589 answers
70,871 users