1. Argue persuasively that there is an algorithm by which to determine, given a context-free grammar G (or, respectively, a PDA M) and a positive integer n, whether or not L(G) (respectively, L(M)) contains at least one string of length less than n.
Hint: One way to solve the problem makes use of Linz's Theorems 8.5 and 8.6 (and the fact that Theorem 8.5's proof (that CFL's are closed under intersection with regular languages) is constructive).
2. Relevant to this problem are the following Java classes:
This problem asks the student to develop two Turing machines, the descriptions of which must be in the format expected by the TM_App program mentioned above. This format is described in comments found within that program and is exemplified by the contents of these two files:
(a) Describe a Turing machine that computes the function half(n) = n/2, where the input and output are to be encoded using unary notation. For example, the value 5 would be encoded by 11111 (i.e., a sequence of five 1's). The machine's initial state should be state zero. The machine should be designed under the assumption that it begins execution in its initial state with the read/write head scanning the tape square holding the leftmost symbol of the input string. Submit this in a file named tm_halve.txt.
(b) Describe a Turing machine that computes the function log2(n) = ⌊log2(n)⌋, again where the input and output are to be encoded using unary notation. As you should know, ⌊log2(n)⌋ is the number of times you can halve a positive integer until you reach the value 1. For example, ⌊log2(21)⌋ = 4, because successive halving of 21 produces the sequence [10, 5, 2, 1]. which has length four.
Hint: It should be evident that a solution to part (a) can be utilized to produce a solution to part (b).
Note: Part (a) will count as 75% of the score for this problem.
3. Present a convincing argument that if S1 and S2 are countable sets, then so is their union, S1 ∪ S2.
Hint: Let fi (i=1,2) be such that Si = { fi(1), fi(2), fi(3), ... }. Describe a function g such that S1 ∪ S2 = { g(1), g(2), g(3), ... }.
4. Present a convincing argument that the set ℤ×ℤ (i.e., the set { (k,m) | k,m are integers }) is countable.
Hint: You can make use of the fact that ℕ×ℕ (the set of ordered pairs of nonnegative integers) is countable, as we proved in class.
5. Present a convincing argument that L is recursive if it has an enumeration procedure that "prints" its members in ascending order by length (so that for any two strings printed consecutively, the second is at least as long as the first).
Hint: Describe a decision algorithm for L that makes use of the enumeration procedure just described. Don't forget that there are only finitely many strings of any particular length.
6. Present a convincing argument that the problem of deciding whether a given Turing machine accepts all input strings (over its input alphabet) is undecidable.
Hint: Describe a reduction to this problem from the Halting Problem. That is, assume that a Java method that solves this problem exists, and make use of it in devising a Java method that solves the Halting Problem. Take note of the reduction that was described for the Halts on Empty Input problem (see relevant web page).