Register

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

328 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

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
411
views
0 answers
0 votes
admin asked Oct 20, 2019
411 views
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input ... $E_{2DFA}$ is not decidable.
User Avatar
1.1k
views
0 answers
1 votes
admin asked Oct 19, 2019
1,126 views
Michael Sipser Edition 3 Exercise 5 Question 15 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate this problem as a language and show that it is decidable.
User Avatar
Link Copied!