theory of computation

Question

EQ(P1,P2)={<P1,P2>∣P1 and P2 are pushdown automata such that L(P1)=L(P2)}

 

EQN(D1,D2)={<D1,D2>∣D1 and D2 are DFAs such that |L(D1)|=|L(D2)|}

Which of the following is correct?

 

 

A. EQ(P1,P2) is decidable but EQN(D1,D2) is not

 

 

B.  EQN(D1,D2) is decidable but EQ(P1,P2) is not

 

 

C. Both EQ(P1,P2) and EQN(D1,D2) are decidable

 

 

D. Both EQ(P1,P2) and EQN(D1,D2) are not decidable

Comments

@technicalguy , what is the source of question ?

Answer 1

The description of first language suggests about the equivalence of two context free languages which we know is undecidable.Hence the first problem is undecidable..

The second problem says whether 2 DFAs accept same number of strings..Let us have 2 DFAs which produce finite regular language then it is fine as we can enumerate number of strings for each DFA and hence we can compare..

Now for infinite language we do not know whether they are accepting equal number of strings or not as infinite is not defined and so is comparison of infinite with infinite..Hence it should be undecidable.

Hence D) should be correct answer..However , if the second language were L(M1) = L(M2) , then it would have been decidable as the minimal DFA for both DFAs must be same in order to achieve equivalence..

Comments

@Arjun sir , counter example for two infinite languages having same cardinalities of string acceptance :

L1  =  a* and  L2  = a+ .. Now both of these are infinite ..But can we say their cardinalities same.I think no bcoz  no matter how many a's we give, both L1 and L2 will accept but L2 will not accept epsilon which L1 will accept which is where cardinality differs..

Hence it is a non trivial property of language..

---

Is there any wrong in my example given..Why it has been downvoted ??\

---

@Habib Good one; I'm not a theoretician so not sure what to select. But pretty sure such questions are out of GATE scope :)