edited by
177 views
0 votes
0 votes

Tell whether each of the following instances of $PCP$ has a solution. Each is presented as two lists $A$ and $B$, and the $i^{th}$ strings on the two lists correspond for each $i = 1,2,\cdot\cdot\cdot\cdot$

  1. $A=(01,001,10); \ B = (011,10,00).$
  2. $A=(01,001,10); \ B = (011,01,00).$
  3. $A=(ab,a,bc,c); \ B = (bc,ab,ca,a).$  
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
admin asked Jul 21, 2019
165 views
Suppose we limited $PCP$ to a one-symbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?