Spring 2000

Homework

- 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.**

- What does Goedel's incompleteness theorem say and why was it
a disappointment to Hilbert?
- Name seven different but equivalent models of computation.
- Exercise 2.12.
- Exercise 2.13 (just the first question).
- 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.
- Exercise A.5 (in the appendix).
- Exercise A.8 (in the appendix).
- 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.) - Exercise 3.4.
- Write a regular expression for the language in part 3 of Exercise 3.4.
- Write a regular grammar for the language in part 2 of Exercise 3.4.
- Exercise 3.7.

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

- Exercise 3.9. Just draw the NFAs and don't do the lower bounds.
- 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.
- Exercise 3.17, parts 2, 4, 6, 7, 9.
- 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.
- 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

- Devise a context-free grammar for the set of all strings over {a,b}
that have twice as many b's as a's.
- 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.**

- 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).
- L = {w : w is a string of a's and b's containing twice as many a's as b's}
- L = {a^{2i} b^i : i >= 0}
- L = {a^{2i} b^{3i} : i >= 0}
- L = {a^i b^j c^k : i = j or j = k}

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

- Prove or disprove: If L is any context-free language and F is any
finite set, then L - F is context-free.
- 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.
- 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).
- 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.**

- 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.)
- The language is regular.
- The language contains the string 11011.
- The language contains an even number of strings.
- The language contains an uncountable number of strings.
- The language is equal to {0,1}*.

- Exercise 6.2 (on p. 173). Use a Turing reduction.
- Exercise 6.3 (on p. 175).
- Exercise 6.6 (on p. 188).
- Exercise 6.8 (on p. 194).
- Exercise 6.18 (on p. 220). Click here for a hint.

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

- Exercise 7.21 (on p. 276).
- Exercise 7.23 (on p. 277). **CORRECTION on 4/10, it said 7.21 before**
- Exercise 7.27, parts 1 and 2 (on pp. 277-278).

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

- Explain Example 8.2 on p. 311 in your own words.
- Exercise 8.20, part 3.