**Problem 1**:
We can enumerate the ordered pairs of positive integers, [1,1], [2,1], [3,1],
[2,2], [4,1], [3,2], [5,1],... first by sum and then by the first (larger) element.
Give the function f(i,j), where i ≥ j, such that the pair [i,j] is the
f(i,j)-th element of the list.

**Problem 2**:
Let L be the set of Turing machine codes M such that L(M) contains at least
two strings. By Rice's theorem, L is not recursive. Show that L is recursively
enumerable by constructing a Turing machine that accepts L.
The description can be informal. Just remember to give the key ideas so the
reader is convinced you understand how the TM works.
A Hint is available.

**Problem 3**:
Devise an encoding with a finite alphabet for all context-free grammars with terminal
alphabet {0,1}. Remember that CFG's may have any number of variables, so you will have
to find a naming system for them. Incidentally, you can extend the encoding (but you
don't have to in this problem) so the grammars may have any terminal alphabet. But since
the encoding must us a finite alphabet, you would not be able to retain the identity
of the terminal symbols. Thus, for example, {0^{n}1^{n} | n ≥ 1}
would look like the same language as {a^{n}b^{n} | n ≥ 1}. For most
purposes that is not important. For example the test for emptiness of a CFL does not
really depend on what the terminals are named.