If PCP is decidable then MPCP is

Related MCQs

• PCP is:
• Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.
• Which of the following statements is/are FALSE? (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. (2) Turing recognizable languages are closed under union and complementation. (3) Turing decidable languages are closed under intersection and complementation (4) Turing recognizable languages are closed under union and intersection.
• Which one of the following is not decidable?
• Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is
• If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be
• If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be
• If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
• If G is a connected planar graph of v vertices e edges and r regions then
• If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is