Register

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

• edited by
250 views
0 votes
0 votes
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 by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
3
admin asked Oct 19, 2019
316 views
Michael Sipser Edition 3 Exercise 5 Question 19 (Page No. 240)
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.
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.
User Avatar
0 votes
0 votes
0 answers
4
admin asked Oct 19, 2019
489 views
Michael Sipser Edition 3 Exercise 5 Question 18 (Page No. 240)
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.
User Avatar
Link Copied!