Chapter 5: Q32P (page 241)
Prove that the following two languages are undecidable.
- and are CFGs where. (Hint: Adapt the hint in Problem 5.21.)
- .
Short Answer
- OVERLAPCFG is undecidable.
- PREFIX - FREECFG is undecidable.
Chapter 5: Q32P (page 241)
Prove that the following two languages are undecidable.
All the tools & learning materials you need for study success - in one app.
Get started for freeQuestion: In the proof of Theorem 5.15, we modified the Turing machine M so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to M . Modify the PCP construction to handle this case.
Show that the Post Correspondence Problem is decidable over the unary alphabet.
Show that is a transitive relation?
Use Rice’s theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages.
Question: Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
What do you think about this solution?
We value your feedback to improve our textbook solutions.