Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged post-correspondence-problem
5
votes
1
answer
1
GO Classes Test Series 2023 | Theory of Computation | Test 5 | Question: 8
Consider the following instance of Post's Correspondence Problem: ... The above instance of Post's Correspondence Problem has : Exactly one solution At least one solution Infinite solutions No solution
Consider the following instance of Post's Correspondence Problem:$$\begin{array}{c|c|c} \text{Index} & \text{A} & \text{B} \\\hline 1 & 10 & 101 \\2 & 101 & 011 \\3 & 110...
GO Classes
274
views
GO Classes
asked
Aug 1, 2022
Theory of Computation
goclasses2024-toc-5-weekly-quiz
goclasses
theory-of-computation
post-correspondence-problem
2-marks
+
–
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
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.)
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$. Given an instance...
admin
395
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
reduction
post-correspondence-problem
decidability
proof
+
–
0
votes
0
answers
3
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.
admin
318
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
+
–
0
votes
0
answers
4
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\}$.
admin
493
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
+
–
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 5 Question 17 (Page No. 240)
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.
admin
263
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
+
–
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 5 Question 8 (Page No. 239)
In the proof of Theorem $5.15$, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to $M$. Modify the $PCP$ construction to handle this case.
In the proof of Theorem $5.15$, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make...
admin
315
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
post-correspondence-problem
proof
+
–
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 5 Question 3 (Page No. 239)
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}$
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}\bi...
admin
253
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
post-correspondence-problem
proof
+
–
0
votes
0
answers
8
Ullman (TOC) Edition 3 Exercise 9.4 Question 3 (Page No. 412)
Suppose we limited $PCP$ to a one-symbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?
Suppose we limited $PCP$ to a one-symbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?
admin
166
views
admin
asked
Jul 21, 2019
Theory of Computation
ullman
theory-of-computation
undecidable
post-correspondence-problem
descriptive
+
–
0
votes
0
answers
9
Ullman (TOC) Edition 3 Exercise 9.4 Question 2 (Page No. 412)
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$.
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 $\Sigm...
admin
190
views
admin
asked
Jul 21, 2019
Theory of Computation
ullman
theory-of-computation
undecidable
post-correspondence-problem
descriptive
+
–
0
votes
0
answers
10
Ullman (TOC) Edition 3 Exercise 9.4 Question 1 (Page No. 412)
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).$
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...
admin
180
views
admin
asked
Jul 21, 2019
Theory of Computation
ullman
theory-of-computation
post-correspondence-problem
descriptive
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register
