Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
Recent questions tagged decidability
2
votes
3
answers
31
Applied roots test series question.
Which of the following is/are undecidable? A = { M| M is TM that accepts exactly all the odd length strings} L = { M|M is a TM and L(M) is infinite} EQ = {<D,E> | D is a DFA , E is a regular expression and L(D) = L(E ... According the key option a' is also UNDECIDABLE why is that, where am I going wrong and is the idea I've thought for option b' correct?
Which of the following is/are undecidable? A = { M| M is TM that accepts exactly all the odd length strings} L = { M|M is a TM and L(M) is infinite} EQ = {<D,E | D is a ...
srjsunny123
575
views
srjsunny123
asked
Sep 6, 2021
Theory of Computation
decidability
+
–
32
votes
1
answer
32
GATE CSE 2021 Set 2 | Question: 36
Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true
Consider the following two statements about regular languages:$S_1$: Every infinite regular language contains an undecidable language as a subset.$S_2$:...
Arjun
12.0k
views
Arjun
asked
Feb 18, 2021
Theory of Computation
gatecse-2021-set2
theory-of-computation
regular-language
decidability
2-marks
+
–
14
votes
5
answers
33
GATE CSE 2021 Set 1 | Question: 39
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$ ... decidable $L_1$ is decidable and $L_2$ is undecidable $L_1$ is undecidable and $L_2$ is decidable Both $L_1$ and $L_2$ are undecidable
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages.$$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text...
Arjun
9.9k
views
Arjun
asked
Feb 18, 2021
Theory of Computation
gatecse-2021-set1
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
easy
2-marks
+
–
9
votes
1
answer
34
GATE Overflow Test Series | Mock GATE | Test 2 | Question: 64
Let $D_1$ and $D_2$ be two Deterministic Pushdown Automata. Which of the following problems is/are undecidable? (Mark all the appropriate choices) Is $L(D_1)\cap L(D_2)$ a Deterministic-CFL? Is $L(D_1)\cap L(D_2) = \emptyset?$ Is $L(D_1)\cup L(D_2)$ a Deterministic-CFL? Is $L(D_1)\cup L(D_2)=\sigma^*?$
Let $D_1$ and $D_2$ be two Deterministic Pushdown Automata. Which of the following problems is/are undecidable? (Mark all the appropriate choices)Is $L(D_1)\cap L(D_2)$ a...
gatecse
567
views
gatecse
asked
Jan 17, 2021
Theory of Computation
go2025-mockgate-2
decidability
context-free-language
multiple-selects
+
–
3
votes
2
answers
35
UGC NET CSE | October 2020 | Part 2 | Question: 55
Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems: Is $L(G_1)=L(G_2)$? Is $L(G_2) \leq L(G_1)$? Is $L(G_1)=R$? Which of the problems are undecidable? Choose the correct answer from the ... given below: $(i)$ only $(ii)$ only $(i)$ and $(ii)$ only $(i)$, $(ii)$ and $(iii)$
Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems:Is $L(G_1)=L(G_2)$?Is $L(G_2) \leq L(G_1)$?...
go_editor
1.1k
views
go_editor
asked
Nov 20, 2020
Theory of Computation
ugcnetcse-oct2020-paper2
theory-of-computation
decidability
+
–
1
votes
1
answer
36
UGC NET CSE | October 2020 | Part 2 | Question: 87
Given below are two statements: Statement $I$: The problem Is $L_1 \wedge L_2 = \phi$? is undecidable for context sensitive languages $L_1$ and $L_2$ Statement $II$: The problem Is $W \in L$? is decidable for context ... are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
Given below are two statements:Statement $I$: The problem “Is $L_1 \wedge L_2 = \phi$?” is undecidable for context sensitive languages $L_1$ and $L_2$Statement $II$: ...
go_editor
1.0k
views
go_editor
asked
Nov 20, 2020
Theory of Computation
ugcnetcse-oct2020-paper2
theory-of-computation
decidability
+
–
9
votes
1
answer
37
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 30
$D_1$ and $D_2$ are Deterministic Pushdown Automata and $E$ is a Finite Automaton. Which of the following problems is/are decidable? (Mark all the appropriate choices) Is $L(D_1)\cap L(D_2)$ a Deterministic-CFL? Is $L(D_1)\cap L(D_2) = \emptyset?$ Is $L(D_1)\subseteq L(E)?$ Is $L(E)\subseteq L(D_1)?$
$D_1$ and $D_2$ are Deterministic Pushdown Automata and $E$ is a Finite Automaton. Which of the following problems is/are decidable? (Mark all the appropriate choices)Is ...
gatecse
552
views
gatecse
asked
Sep 29, 2020
Theory of Computation
go2025-toc-1
decidability
multiple-selects
+
–
1
votes
2
answers
38
NIELIT 2017 DEC Scientist B - Section B: 11
Which of the following are undecidable? $P1$: The language generated by some CFG contains any words of length less than some given number $n$. $P2$: Let $L1$ be CFL and $L2$ be regular, to determine whether $L1$ and $L2$ have common elements $P3$: ... to determine whether epsilon belongs to $L(G)$ $P2$ only $P1$ and $P2$ only $P2$ and $P3$ only $P3$ only
Which of the following are undecidable?$P1$: The language generated by some CFG contains any words of length less than some given number $n$.$P2$: Let $L1$ be CFL and $L2...
admin
2.1k
views
admin
asked
Mar 30, 2020
Theory of Computation
nielit2017dec-scientistb
theory-of-computation
decidability
+
–
31
votes
7
answers
39
GATE CSE 2020 | Question: 26
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M.$L_1 = \{\left \langle M \right \r...
Arjun
14.5k
views
Arjun
asked
Feb 12, 2020
Theory of Computation
gatecse-2020
theory-of-computation
decidability
2-marks
+
–
3
votes
4
answers
40
TIFR CSE 2020 | Part B | Question: 2
Consider the following statements. The intersection of two context-free languages is always context-free The super-set of a context-free languages is never regular The subset of a decidable language is always decidable Let $\Sigma = \{a,b,c\}.$ Let $L\subseteq \Sigma$ be the language of ... Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
Consider the following statements.The intersection of two context-free languages is always context-freeThe super-set of a context-free languages is never regularThe subse...
admin
1.5k
views
admin
asked
Feb 10, 2020
Theory of Computation
tifr2020
theory-of-computation
context-free-language
decidability
+
–
3
votes
0
answers
41
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 CF...
admin
631
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
recursive-and-recursively-enumerable-languages
decidability
proof
+
–
1
votes
0
answers
42
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...
admin
337
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
proof
+
–
0
votes
1
answer
43
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.
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 you...
admin
723
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
1
votes
2
answers
44
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.
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 ...
admin
585
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
pushdown-automata
decidability
proof
+
–
0
votes
0
answers
45
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}\}$.
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\}$.$PREF...
admin
455
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
turing-machine
decidability
proof
+
–
0
votes
0
answers
46
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.
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 inte...
admin
362
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
1
votes
0
answers
47
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} \}$.
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 lan...
admin
393
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
+
–
0
votes
0
answers
48
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.
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 languag...
admin
457
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
+
–
0
votes
0
answers
49
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.
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 languag...
admin
411
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
+
–
1
votes
0
answers
50
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.
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$. The squares along the boundary of th...
admin
467
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
+
–
0
votes
0
answers
51
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.
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 in...
admin
395
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
+
–
0
votes
0
answers
52
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}$.
admin
301
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
+
–
0
votes
0
answers
53
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
admin
201
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
decidability
reduction
proof
+
–
0
votes
0
answers
54
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.)
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$. Given an instance...
admin
395
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
reduction
post-correspondence-problem
decidability
proof
+
–
0
votes
0
answers
55
Michael Sipser Edition 3 Exercise 5 Question 20 (Page No. 240)
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .
admin
288
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
56
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.
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.
admin
316
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
+
–
0
votes
0
answers
57
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\}$.
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.
admin
489
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
+
–
0
votes
0
answers
58
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\}$.
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.
admin
263
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
post-correspondence-problem
decidability
proof
+
–
1
votes
0
answers
59
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.
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 t...
admin
1.0k
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
60
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.
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. Formulat...
admin
277
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
Page:
« prev
1
2
3
4
5
6
7
...
16
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register
