Register

Recent questions tagged michael-sipser

0 votes
0 answers
61
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
62
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
63
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
65
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
70
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
72
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
76
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
79
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
0 votes
1 answer
90
Michael Sipser Edition 3 Exercise 3 Question 4 (Page No. 187)
Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.
Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enume...
User Avatar
Page: