These exerrcises are from Sipser.

1. 4.5 (page 169). Hint. Think about how you would tell if a given DFA accepts infinitely many different strings. What would you look for?. Be careful to check that an accepting state is accessible from whatever feature you find.

2. 4.18 (page 170). Hint. Work the following steps.

   1. Read the problem carefully. Draw a picture (a Venn diagram) showing the sets A, B, C and C-bar.

   2. What is A-bar union B-bar?

   3. You know that A and B are each co-turing-recognizable. That tells you that some programs exist. Gives names to those programs. What do they do?

   4. Use the programs from the preceding part to write a program that solves C. Do not try to define C ahead of time. Instead, let your new program be the definition of C. Design your new program so that it answers yes on inputs that are in A (i.e. not in A-bar) and answers no on inputs that are in B (i.e. not in B-bar). It does not matter what it answers on inputs that are in neither A nor B; it just has to give some answer.

3. 5.17 (page 195). Hint. Think about what the solutions of a PCP instance look like when the alphabet only has one character. Note that the only characteristic of each string that is of any interest is its length. So the problem should amount to an arithmetic problem.

4. 5.18 (page 195). Hint: Perform a reduction from (PCP) to (PCP with a two-element alphabet). You can encode a large alphabet using a two-element alphabet.