Register
Filter

Recent questions without answers

0 votes
0 answers
3721
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
3722
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
3723
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
3724
Michael Sipser Edition 3 Exercise 4 Question 9 (Page No. 211)
Review the way that we define sets to be the same size in Definition $4.12$ (page $203$). Show that “is the same size” is an equivalence relation.
Review the way that we define sets to be the same size in Definition $4.12$ (page $203$). Show that “is the same size” is an equivalence relation.
User Avatar
0 votes
0 answers
3726
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
0 votes
0 answers
3731
Michael Sipser Edition 3 Exercise 4 Question 2 (Page No. 211)
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
User Avatar
0 votes
0 answers
3733
Michael Sipser Edition 3 Exercise 3 Question 22 (Page No. 190)
Let $A$ be the language containing only the single string $s$ ... of this problem, assume that the question of whether life will be found on Mars has an unambiguous $YES$ or $NO$ answer.
Let $A$ be the language containing only the single string $s$, where$s = \left\{\begin{matrix} \text{0 if life never will be found on Mars} \\ \:\: \text{1 if life will b...
User Avatar
0 votes
0 answers
3737
Michael Sipser Edition 3 Exercise 3 Question 18 (Page No. 190)
Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
User Avatar
0 votes
0 answers
3740
Michael Sipser Edition 3 Exercise 3 Question 15 (Page No. 189)
Show that the collection of decidable languages is closed under the operation of union. concatenation. star. complementation. intersection.
Show that the collection of decidable languages is closed under the operation ofunion.concatenation.star.complementation.intersection.
User Avatar
Page: