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ⁿ1ⁿ | n ≥ 1} would look like the same language as {aⁿbⁿ | 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.