Register

Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)

• edited by
185 views

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

249
views
0 answers
0 votes
admin asked Oct 19, 2019
249 views
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.
User Avatar
329
views
0 answers
0 votes
admin asked Oct 19, 2019
329 views
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}$.
User Avatar
244
views
1 answers
0 votes
admin asked Oct 19, 2019
244 views
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
User Avatar
419
views
0 answers
0 votes
admin asked Oct 19, 2019
419 views
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.)
User Avatar
Link Copied!