Register

Materials:

Recent questions tagged decidability

0 votes
0 answers
65
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.
Let $T = \{\langle M \rangle \mid \text{M is a TM that accepts $w^{R}$ whenever it accepts} \:w\}$. Show that $T$ is undecidable.
User Avatar
0 votes
0 answers
71
Michael Sipser Edition 3 Exercise 4 Question 29 (Page No. 212)
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly $k$ strings where $k \geq 0$ or $k = \infty$}\}$. Show that $C_{CFG}$ is decidable.
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly $k$ strings where $k \geq 0$ or $k = \infty$}\}$. Show that $C_{CFG}$ is decidable...
User Avatar
0 votes
0 answers
73
Michael Sipser Edition 3 Exercise 4 Question 27 (Page No. 212)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 votes
1 answer
74
Michael Sipser Edition 3 Exercise 4 Question 26 (Page No. 212)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 votes
0 answers
79
Michael Sipser Edition 3 Exercise 4 Question 21 (Page No. 212)
Let $S = \{\langle M \rangle \mid \text{M is a DFA that accepts}\: \text{ $w^{R}$ whenever it accepts $w$}\}$. Show that $S$ is decidable.
Let $S = \{\langle M \rangle \mid \text{M is a DFA that accepts}\: \text{ $w^{R}$ whenever it accepts $w$}\}$. Show that $S$ is decidable.
User Avatar
0 votes
0 answers
82
Michael Sipser Edition 3 Exercise 4 Question 17 (Page No. 212)
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
User Avatar
0 votes
0 answers
86
Michael Sipser Edition 3 Exercise 4 Question 13 (Page No. 211)
Let $A = \{ \langle{ R, S \rangle} \mid \text{R and S are regular expressions and} \: L(R) \subseteq L(S)\}$. Show that $A$ is decidable.
Let $A = \{ \langle{ R, S \rangle} \mid \text{R and S are regular expressions and} \: L(R) \subseteq L(S)\}$. Show that $A$ is decidable.
User Avatar
0 votes
0 answers
87
Michael Sipser Edition 3 Exercise 4 Question 12 (Page No. 211)
Let $A = \{\langle{ M \rangle} \mid \text{M is a DFA that doesn’t accept any string containing an odd number of 1s}\}$.Show that $A$ is decidable.
Let $A = \{\langle{ M \rangle} \mid \text{M is a DFA that doesn’t accept any string containing an odd number of 1s}\}$.Show that $A$ is decidable.
User Avatar
0 votes
0 answers
88
Michael Sipser Edition 3 Exercise 4 Question 11 (Page No. 211)
Let $INFINITE_{PDA} = \{\langle{ M \rangle} \mid \text{M is a PDA and L(M) is an infinite language}\}$. Show that $INFINITE_{PDA}$ is decidable.
Let $INFINITE_{PDA} = \{\langle{ M \rangle} \mid \text{M is a PDA and L(M) is an infinite language}\}$. Show that $INFINITE_{PDA}$ is decidable.
User Avatar
0 votes
0 answers
89
Michael Sipser Edition 3 Exercise 4 Question 10 (Page No. 211)
Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.
Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.
User Avatar
0 votes
0 answers
90
Michael Sipser Edition 3 Exercise 4 Question 7 (Page No. 211)
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.
User Avatar
Page: