Homework 12

Details

1. 5.1
2. 5.2
3. 5.3
4. 5.4
5. 5.17
6. 5.18
7. 5.19
8. 5.23

• 5.1 is easy if you choose the correct undecidable problem to reduce from. I'll give you a hint: reduce from one of the undecidable languages related to CFGs. It also might be helpful to recall that the top of page 199 implies that SOMETHING_CFG is decidable iff SOMETHING_PDA is decidable.
• For 5.2, construct a TM that can recognize the complement of EQ_CFG. In other words, all strings that are not of the form in the definition of EQ_CFG. And remember, you only need to recognize.
• For 5.3, write a computer program to solve it. Oh wait. Never mind. But a little trial-and-error should yield a solution. I know there is a solution with 7 dominos. There may or may not be a shorter one. I tell you this so you don't give up too quickly.
• For 5.4, if you can find a mapping from any non-regular language to any regular language, that would be proof that the statement is not true. Don't forget that a mapping reduction is computed using a Turing machine, so you have more power at your disposal than DFAs, CFGs, etc.
• For 5.17, provide a TM and explain why it works.
• For 5.18, reduce from the normal PCP. Thinking in terms of binary representations of things is a good start, but you need to be careful. It is easy to ensure that if an instance w of PCP has a match, then f(w) will have a match in BPCP. However, if you are not careful, it may be possible for f(w) to have a match in BPCP when w does not have a match in PCP.
• For 5.23, notice the iff. In other words, you need to prove both directions. And don't over think it. You don't need a fancy mapping--you just need to ensure that something in A maps to something in 0^*1^* and something not in A does not. It doesn't matter exactly WHAT strings you map to as long as that property holds.