3.6 Chapter 3

Complete the following problems:

1. (0.30) Consider the non-context-free language B from the textbook problem 2.31 (pg 157) (all palindromes over of {0,1} with an equal number of 0s and 1s):

   1. (0.20) Give the 7-tuple for the machine, including a detailed state diagram.

   2. (0.05) Show the sequence of configurations (forming a computation history) for the machine on 0110.

   3. (0.05) Show the sequence of configurations (forming a computation history) for the machine on 01110.

2. (0.20) Consider the non-context-free language L3 from Chapter 2.4. Give an implementation-level (high-level) description for a Turing machine that recognizes L3.

3. (0.20) Do problem 3.15(c) from the textbook (pg 189). This is the one about decidable languages being closed under star.

4. (0.20) Do problem 3.16(b) from the textbook (pg 189). This is the one about Turing-recognizable languages being closed under concatenation.

5. (0.10) Find all integral roots (if any exist) of f(x) = x^3 - 3x^2 - 6x + 8. (Hint: You are in a computer science class and section 3.3 of the textbook talks about this kind of problem.)