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
0
votes
0
answers
1
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

2
views
michaelsipser
theoryofcomputation
contextfreegrammars
reduction
postcorrespondenceproblem
decidability
proof
0
votes
0
answers
2
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

3
views
michaelsipser
theoryofcomputation
postcorrespondenceproblem
decidability
proof
0
votes
0
answers
3
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

3
views
michaelsipser
theoryofcomputation
postcorrespondenceproblem
decidability
proof
0
votes
0
answers
4
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

3
views
michaelsipser
theoryofcomputation
postcorrespondenceproblem
decidability
proof
0
votes
0
answers
5
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

7
views
michaelsipser
theoryofcomputation
turingmachine
postcorrespondenceproblem
proof
0
votes
0
answers
6
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

14
views
ullman
theoryofcomputation
undecidable
postcorrespondenceproblem
descriptive
0
votes
0
answers
7
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

9
views
ullman
theoryofcomputation
undecidable
postcorrespondenceproblem
descriptive
0
votes
0
answers
8
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged postcorrespondenceproblem
Recent Blog Comments
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
bro can be upload all standard book questions in...
it'll take 34 days but for most purpose you can...
50,648
questions
56,422
answers
195,194
comments
99,825
users