The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged postcorrespondenceproblem
+1
vote
1
answer
1
NTA NET DEC 2019 (Postcorrespondence)
$\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{\; 4) \;Neither \;(A,B) \;nor\; (C,D) }$
asked
Dec 20, 2019
in
Algorithms
by
Sanjay Sharma
Boss
(
49.3k
points)

73
views
post
postcorrespondenceproblem
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.)
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

5
views
michaelsipser
theoryofcomputation
contextfreegrammars
reduction
postcorrespondenceproblem
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.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

5
views
michaelsipser
theoryofcomputation
postcorrespondenceproblem
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\}$.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

9
views
michaelsipser
theoryofcomputation
postcorrespondenceproblem
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\}$.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

9
views
michaelsipser
theoryofcomputation
postcorrespondenceproblem
decidability
proof
0
votes
0
answers
6
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}$
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

9
views
michaelsipser
theoryofcomputation
turingmachine
postcorrespondenceproblem
proof
0
votes
0
answers
7
Ullman (TOC) Edition 3 Exercise 9.4 Question 3 (Page No. 412)
Suppose we limited $PCP$ to a onesymbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?
asked
Jul 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

16
views
ullman
theoryofcomputation
undecidable
postcorrespondenceproblem
descriptive
0
votes
0
answers
8
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$.
asked
Jul 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

12
views
ullman
theoryofcomputation
undecidable
postcorrespondenceproblem
descriptive
0
votes
0
answers
9
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).$
asked
Jul 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.8k
points)

13
views
ullman
theoryofcomputation
postcorrespondenceproblem
descriptive
To see more, click for the
full list of questions
or
popular tags
.
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged postcorrespondenceproblem
Recent Blog Comments
100 percent
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....
absolutely right
50,737
questions
57,286
answers
198,193
comments
104,872
users