menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
IIT Interview Experiences (Patna, Jodhpur and Hyd)
IIT Madras Direct PhD Interview Experience-July 2020
IIT Hyderabad M.Tech RA CSE Interview Experience-July 2020
IIT Hyderabad AI M.tech RA Interview Experience-July 2020
GATE 2021 BROCHURE
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.5k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.4k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent Blog Comments
it'll be automatic.
@gatecse Suppose if someone is the top user of...
Thanks for the clarification.
"Weekly Top User": It is only one person per...
gatecse Even my name is showing in the list of...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
0
votes
33
views
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.
michael-sipser
theory-of-computation
turing-recognizable-languages
decidability
reduction
proof
asked
Oct 19, 2019
in
Theory of Computation
Lakshman Patel RJIT
33
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
0
Answers
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
0
votes
0
answers
1
20
views
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
asked
Oct 19, 2019
in
Theory of Computation
Lakshman Patel RJIT
20
views
michael-sipser
theory-of-computation
turing-recognizable-languages
reduction
proof
3
votes
0
answers
2
175
views
Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
Lakshman Patel RJIT
175
views
michael-sipser
theory-of-computation
context-free-grammars
turing-recognizable-languages
decidability
proof
1
vote
0
answers
3
71
views
Michael Sipser Edition 3 Exercise 5 Question 35 (Page No. 242)
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
Lakshman Patel RJIT
71
views
michael-sipser
theory-of-computation
turing-recognizable-languages
decidability
proof
0
votes
0
answers
4
32
views
Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
asked
Oct 19, 2019
in
Theory of Computation
Lakshman Patel RJIT
32
views
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
...