Question

State true or false:

Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.

(a) Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.

(b) true

(c) false

This question was posed to me by my college director while I was bunking the class.

My enquiry is from Rice’s Theorem, Properties and PCP topic in section Undecidability of Automata Theory

Answer 1

The correct option is (a) Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.

The best explanation: The MPCP is : Given lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..wir = x1xi1xi2…xir?