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 turingrecognizablelanguages
+2
votes
0
answers
1
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.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

90
views
michaelsipser
theoryofcomputation
contextfreegrammars
turingrecognizablelanguages
decidability
proof
+1
vote
0
answers
2
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 Turingrecognizable. Show that $NECESSARY_{CFG} $is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

34
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
decidability
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 5 Question 24 (Page No. 240)
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turingrecognizable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

6
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turingrecognizable iff $A \leq_{m} A_{TM}$.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

6
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
reduction
proof
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
Show that if $A$ is Turingrecognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

13
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
decidability
reduction
proof
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 5 Question 2 (Page No. 239)
Show that $EQ_{CFG}$ is coTuringrecognizable.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

15
views
michaelsipser
theoryofcomputation
contextfreegrammars
turingrecognizablelanguages
proof
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 4 Question 30 (Page No. 212)
Let $A$ be a Turingrecognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not ... $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

8
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
decidability
proof
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 4 Question 20 (Page No. 212)
Let $A$ and $B$ be two disjoint languages. Say that language $C$ separates $A$ and $B$ if $A \subseteq C$ and $B \subseteq \overline{C}$. Show that any two disjoint coTuringrecognizable languages are separable by some decidable language.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

16
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
proof
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 4 Question 18 (Page No. 212)
Let $C$ be a language. Prove that $C$ is Turingrecognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y (\langle{ x, y \rangle} \in D)\}$.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

5
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
decidability
proof
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 4 Question 5 (Page No. 211)
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turingrecognizable.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

4
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 3 Question 20 (Page No. 190)
Show that singletape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

8
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 3 Question 19 (Page No. 190)
Show that every infinite Turingrecognizable language has an infinite decidable subset.
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

9
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
13
Michael Sipser Edition 3 Exercise 3 Question 17 (Page No. 189)
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turingrecognizable language consisting of $TM$ descriptions. Show that there is a decidable language $C$ consisting of $TM$ descriptions such that every machine described in $B$ has an equivalent machine in $C$ and vice versa.
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

4
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 3 Question 16 (Page No. 189)
Show that the collection of Turingrecognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

10
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 3 Question 14 (Page No. 189)
A queue automaton is like a pushdown automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the lefthand end and read only at the righthand end. ... at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turingrecognizable.
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

9
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 3 Question 13 (Page No. 189)
A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,S\}$ At each ... that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

11
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 3 Question 12 (Page No. 189)
A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,RESET\}$ ... to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turingrecognizable languages.
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

18
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 3 Question 11 (Page No. 189)
A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion ... tape as it moves leftward. Show that this type of Turing machine recognizes the class of Turingrecognizable languages.
asked
Oct 15, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

8
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
+3
votes
1
answer
19
GO2019FLT156
Consider the following language $L$: $L=\{<M,x,k> \mid M \text{ is a Turing Machine and M does not halt on x within k steps} \}$ The language family to which $L$ belongs is not closed under? Intersection Homomorphism Set Difference Complementation
asked
Dec 27, 2018
in
Theory of Computation
by
Ruturaj Mohanty
Active
(
3.4k
points)

220
views
go2019flt1
turingrecognizablelanguages
theoryofcomputation
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
Contesting Answer Key Link Is Live Now
Answer keys are released for Gate2020
My Experience at IIT Madras and Some Insights
GATE Meetup at CSA IISC on February 29 as part of CSA Open Day
Make Rank Predictor Dynamic (Again?)
Follow @csegate
Recent questions tagged turingrecognizablelanguages
Recent Blog Comments
Hi Everyone, As anyone who has appeared for ISRO...
So the written test and interview both do not...
So,O(n^2) remains and might be 0(nlogn) further...
Ideally both should be given marks, it shouldn't...
Linked list question can change from 0(n^2) to...
50,833
questions
57,713
answers
199,427
comments
107,660
users