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.

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

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

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

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

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