Michael Sipser Edition 3 Exercise 5 Question 3 (Page No. 239)

21 views
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}$

edited

Related questions

1
30 views
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.)
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.
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.