• The exercise numbers refer to the textbook (Moret).

• Write clearly and legibly. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length.

• Don't forget to acknowledge all sources of assistance, such as people, other textbooks, solution sets, etc.

• Homework is always due at the beginning of class because I might want to go over it that day. Generally late homework is not accepted; but if you have a problem, talk to me in advance.

Problem Set A, due Tue, Feb 1, 2000.

1. What does Goedel's incompleteness theorem say and why was it a disappointment to Hilbert?

2. Name seven different but equivalent models of computation.

3. Exercise 2.12.

4. Exercise 2.13 (just the first question).

5. Let PARITYFUN be the set of all functions f from the natural numbers to the natural numbers such that f(n) is even if n is even and f(n) is odd if n is odd. For example, f(n) = n + 4 is a member of PARITYFUN, but f(n) = 2*n is not. Is the set PARITYFUN countable or uncountable? Prove your answer.

6. Exercise A.5 (in the appendix).

7. Exercise A.8 (in the appendix).

8. A complete binary tree is a rooted tree in which every non-leaf node has exactly two children and every leaf node is the same distance from the root; this distance is the number of edges in the path from the root to the leaf and is called the depth of the tree. Prove by induction that a complete binary tree with depth d has 2^{d+1} - 1 nodes. (That's 2 raised to the power d+1, my html is pretty basic.)

9. Exercise 3.4.

10. Write a regular expression for the language in part 3 of Exercise 3.4.

11. Write a regular grammar for the language in part 2 of Exercise 3.4.

12. Exercise 3.7.

Problem Set B, due Tue, Feb 15, 2000.

1. Exercise 3.9. Just draw the NFAs and don't do the lower bounds.

2. Convert the regular expression (ab U aa)* to an equivalent regular grammar, using all the official transformation algorithms presented in class (don't do any ad hoc optimizations). Then convert your resulting regular grammar back into a regular expression, again using the official transformation algorithms.

3. Exercise 3.17, parts 2, 4, 6, 7, 9.

4. Exercise 3.25, all parts. To prove an assertion, show that it is true for any languages L, L1, and L2 that satisfy the hypotheses. To disprove an assertion, one approach is to demonstrate a specific L (or L1 and L2) for which the assertion is not true.

5. What language is generated by this context-free grammar?

   S -> a S a | b S b | A
   A -> a B b | b B a
   B -> a B a | b B b | a | b | epsilon
   

6. Devise a context-free grammar for the set of all strings over {a,b} that have twice as many b's as a's.

7. Convert the following context-free grammar into an equivalent one that has no direct left-recursion. Use the method presented in class with no ad hoc optimizations.

   S -> A | C
   A -> A a B | A a C | B | a
   B -> B b | C b
   C -> c C | c
   

Problem Set C, due Thursday, Mar 9 (extended), 2000.

1. Devise a push-down automaton for the following languages. For each, first describe in English your plan of attack (the intuition for how you will use the stack to recognize the strings of the language); then list the transitions or draw the state transition diagram (don't forget to indicate on your diagram how the stack is manipulated in each transition).
   1. L = {w : w is a string of a's and b's containing twice as many a's as b's}
   2. L = {a^{2i} b^i : i >= 0}
   3. L = {a^{2i} b^{3i} : i >= 0}
   4. L = {a^i b^j c^k : i = j or j = k}

2. For each of the following languages prove whether it is (i) regular or (ii) context-free but not regular or (iii) not context-free.
   1. L = {xcx : x is a string of a's and b's}
   2. L = {xayb : x and y are strings of a's and b's of the same length}
   3. L = {x : x is a string of a's and b's and the number of b's is the square of the number of a's}
   4. L = {a^n b^m a^n b^{n+m} : m, n >= 0}

3. Prove or disprove: If L is any context-free language and F is any finite set, then L - F is context-free.

4. Exercise 4.2, part 2 (on p. 101). Do all the details and draw a state transition diagram. Also provide English explanation and intuition for how your TM operates.

5. Exercise 4.10 (on p. 117). Describe the simulation at an intuitive level of detail (similar to what was done in class). To make your life simpler, you can assume that the 2-D tape has a a left boundary and a bottom boundary, so that it goes up infinitely and to the right infinitely (but does not go down infinitely or to the left infinitely).

6. Prove that there is no algorithm that determines whether an arbitrary Turing machine halts when run with the input string 11011. Use reduction in your proof.

Problem Set D, due Tuesday, Apr 4, 2000.

1. For each of the following properties of the r.e. languages, prove whether the property is decidable or not. (Don't forget that Rice's theorem can make you life easy in some situations.)
   1. The language is regular.
   2. The language contains the string 11011.
   3. The language contains an even number of strings.
   4. The language contains an uncountable number of strings.
   5. The language is equal to {0,1}*.

2. Exercise 6.2 (on p. 173). Use a Turing reduction.

3. Exercise 6.3 (on p. 175).

4. Exercise 6.6 (on p. 188).

5. Exercise 6.8 (on p. 194).

6. Exercise 6.18 (on p. 220). Click here for a hint.

Problem Set E, due Tuesday, Apr 18, 2000.

1. Exercise 7.21 (on p. 276).

2. Exercise 7.23 (on p. 277). **CORRECTION on 4/10, it said 7.21 before**

3. Exercise 7.27, parts 1 and 2 (on pp. 277-278).

Problem Set F, due Tuesday, May 2, 2000, 5:00 PM.

1. Explain Example 8.2 on p. 311 in your own words.

2. Exercise 8.20, part 3.