Homework 12

General Comments

• Problems are taken from the textbook unless otherwise noted.
• For full credit, provide context for each problem, show all calculations, and explain your work/answers.
• Numbers and/or algebra by themselves are not enough.
• You will lose a significant amount of credit if you do not show enough work/context for your answers.
• Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You must indicate any assistance you had on an assignment as specified on the Policies page.

Details

Problem	Comments
5.1	This 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 SOMETHINGCFG is decidable iff SOMETHINGPDA is decidable.
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.
5.2	Construct a TM that can recognize the complement of EQCFG. In other words, all strings that are not of the form in the definition of EQCFG. And remember, you only need to recognize.
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.
5.17	Provide a TM and explain why it works.
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.
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.