Register

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

243 views

1 Answer

0 votes
0 votes
As 0*1* is RE and it's decidable

As if this is decidable so it's LHS is also deciable
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

328
views
0 answers
0 votes
admin asked Oct 19, 2019
328 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
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
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
185
views
0 answers
0 votes
admin asked Oct 19, 2019
185 views
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
User Avatar
Link Copied!