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 proof
+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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
55
views
michael-sipser
theory-of-computation
context-free-grammars
turing-recognizable-languages
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 Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
16
views
michael-sipser
theory-of-computation
turing-recognizable-languages
decidability
proof
0
votes
1
answer
3
Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
36
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
7
views
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
10
views
michael-sipser
theory-of-computation
context-free-grammars
turing-machine
decidability
proof
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 5 Question 31 (Page No. 241)
Let $f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$ for any natural number $x$. If you start with an integer $x$ and iterate $f$, you ... decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
15
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+1
vote
0
answers
7
Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
14
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal ... that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
6
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
10
views
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$ ... of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
8
views
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape ... $E_{2DFA}$ is not decidable.
asked
Oct 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
5
views
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
0
votes
0
answers
12
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}$.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
10
views
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
0
votes
0
answers
13
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 Turing-recognizable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
3
views
michael-sipser
theory-of-computation
turing-machine
turing-recognizable-languages
proof
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
4
views
michael-sipser
theory-of-computation
decidability
reduction
proof
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
1
view
michael-sipser
theory-of-computation
turing-recognizable-languages
reduction
proof
0
votes
0
answers
16
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
michael-sipser
theory-of-computation
context-free-grammars
reduction
post-correspondence-problem
decidability
proof
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 5 Question 20 (Page No. 240)
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
3
views
michael-sipser
theory-of-computation
decidability
proof
0
votes
0
answers
18
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
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
0
votes
0
answers
19
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
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
0
votes
0
answers
20
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
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 5 Question 16 (Page No. 240)
Let $\Gamma = \{0, 1, \sqcup\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as follows. For each value of $k$, consider all $k-$state TMs that halt when ... maximum number of $1s$ that remain on the tape among all of these machines. Show that $BB$ is not a computable function.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
1
view
michael-sipser
theory-of-computation
turing-machine
computability
proof
+1
vote
0
answers
22
Michael Sipser Edition 3 Exercise 5 Question 15 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate this problem as a language and show that it is decidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
34
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input $w$ ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
1
view
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 5 Question 13 (Page No. 239)
A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
4
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 5 Question 12 (Page No. 239)
Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
8
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 5 Question 11 (Page No. 239)
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
6
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 5 Question 10 (Page No. 239)
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input $w$. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
2
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 5 Question 9 (Page No. 239)
Let $T = \{\langle M \rangle \mid \text{M is a TM that accepts $w^{R}$ whenever it accepts} \:w\}$. Show that $T$ is undecidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
4
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
0
votes
0
answers
29
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.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
2
views
michael-sipser
theory-of-computation
turing-machine
post-corresponding-problem
proof
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)
|
7
views
michael-sipser
theory-of-computation
turing-recognizable-languages
decidability
reduction
proof
Page:
1
2
3
4
5
6
...
9
next »
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 proof
Recent Blog Comments
@
[email protected]
Can this be updated?
Even In 2019 my 16 questions goes for negative...
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...
50,647
questions
56,503
answers
195,502
comments
100,865
users