in Theory of Computation edited by
9,111 views
51 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}$
in Theory of Computation edited by
9.1k views

5 Comments

I am getting answer as option A. but in last row instead of S -> Q | P I am getting S-> P | Q.
19
You are correct. That must be a printing mistake.
3
thanks
0
ans will be option B bcz in last two row entries are (Q,P) and (P,Q)
0

For those finding it difficult to map the states, in ZxY:

Start State → b→ Final State & Final State→ b→ Start State. This can be used to eliminate the options B, C, D. But although A satisfies first three transitions, last one wrongly given in the option.

0

Subscribe to GO Classes for GATE CSE 2022

4 Answers

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

edited by
by

22 Comments

Is there any difference in the product automaton of Z x Y and Y x Z ?
3
Does ZxY means concatenation of automata?
2
No, it is intersection
17
It is product rt?
1
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.
17
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 ? 

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

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

1
@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.
1

@PEKKA 

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

2

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

8
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)

0
You could try NPTEL lectures by Kamala Kritivasan. She provides examples of DFA operations with state tables.
1

$Y:$

$Z:$

$Z\times Y:$


$P=11\ \&\ R=22$

$P\rightarrow b=R\ \&\ R\rightarrow b=P$ $\left(Only\ satisfied\ by\ option\ A\right)$

0
@ayush upadhaya sir mera bhi same table aya ha
0
@arjun sir i think you have made table of y*z which is incorrect
0
21 votes

Correct answer is option A. 

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

edited by

4 Comments

I don't  know even how to do it directly with Transition Table but with Figures, it is very easy.

for avoid confusion rename the states as 1,2,3,4.

and no doubt X means intersection.

0

Your answer is correct.

In option A, S on a goes to Q

0
Hi,

  When we do Z x Y then from Z → a (it goes to state 2), From Y → a (it goes to state 1), from 11 by reading a, it as to go 21, but your transition goes to 12 how?

let me know if I’m wrong?
0
@jeeruajay  You are correct I also got the same.
0
10 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

1 comment

Yes this way we can check the correct option.
0
7 votes

1 comment

@Mostafize Mondal

Bro you did Y X Z. But we have to perform

Z X Y.

But yeah we have to choose option A) ( last two rows are wrong-print mistake)

0
Answer:

Related questions