CS154 Assignment #5 and CS154N Asssignment #1

Due Monday, February 28, 2000, 3:15PM

Note: if you are taking CS154N, you should do only Problems 4 and 5. Please indicate on your assignment that you are in CS154N.

1. (20 pts.; CS154 only) Show that {0^i1^j2^k | i<j<k} is not a context-free language.

2. (20 pts.; CS154 only) As defined on the midterm, if L is a language and a a symbol, a\L is the set of strings w such that aw is in L. Show that if L is a CFL, then so is a\L. You proof need not be extremely detailed, but should have enough detail to convince a TA. In particular, I suggest you talk about the situation where a typical string w is in L or where it is in a\L.

3. (20 pts.; CS154 only) Give an algorithm to decide whether a given CFL contains all strings of 0's. Your algorithm does not have to be efficient. Exaplain why your algorithm works, although you do not have to give a formal proof. Note: This problem is actually quite hard. If we'd asked for ``contains all strings of 0's and 1's,'' there wouldn't even be such an algorithm.

4. (20 pts.) Using the informal notion of programs and questions about programs as in Section 8.1 of the course reader, consider asking whether a program P with input I ever executes an assignment to a variable named x. Prove that there is no program to tell whether this condition holds, by reducing the ``hello, world'' problem to this one. Hint: Remember that the given program in the reduction may have a variable x, and you have to be careful that the program you create in your reduction doesn't accidentally assign to x without your intending it to.

5. (20 pts.) Give the specification (7-tuple plus the rules for delta) for a Turing machine that accepts the language of regular expression a*b*.