# Recent questions tagged post-correspondence-problem

1 vote
1
$\mathbf{Q57}$ Let $\mathrm{A={001,0011,11,101}}$ and $\mathrm{B={01,111,111,010}}$. Similarly , Let $\mathrm{C={00,001,1000}}$ and $\mathrm{B={0,11,011}}$. Which of the following pairs have a post correspondence solution? $\mathrm{1)\; Only \;pair \;(A,B) }$ $\mathrm{ 2) \;Only\; pair \;(C,D) }$ $\mathrm{ 3) \; Both (A,B)\; and (C,D) \; }$ $\mathrm{\; 4) \;Neither \;(A,B) \;nor\; (C,D) }$
2
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)
3
In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.
4
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.
5
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.
6
Find a match in the following instance of the Post Correspondence Problem. $\begin{Bmatrix} \bigg[\dfrac{ab}{abab}\bigg],&\bigg[\dfrac{b}{a}\bigg],&\bigg[\dfrac{aba}{b}\bigg], & \bigg[\dfrac{aa}{a}\bigg] \end{Bmatrix}$
Suppose we limited $PCP$ to a one-symbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?
We showed that $PCP$ was undecidable, but we assumed that the alphabet $\Sigma$ could be arbitrary. Show that $PCP$ is undecidable even if we limit the alphabet to $\Sigma = \left\{0,1\right\}$ by reducing $PCP$ to this special case of $PCP$.
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$ $A=(01,001,10); \ B = (011,10,00).$ $A=(01,001,10); \ B = (011,01,00).$ $A=(ab,a,bc,c); \ B = (bc,ab,ca,a).$