# CS154 Assignment #6 and CS154N Asssignment #2

### Due Monday, March 6, 2000, 3:15PM

1. (20pts.) Some people define a Turing machine to have a tape that is infinite in both directions, with the cells to the left of the initial head position all blank initially. Show that this extension does not add more power to the TM model; i.e., for every TM M_2 with a two-way infinite tape, there is another TM with a one-way infinite tape, M_1, that accepts the same language. Give a detailed construction of the delta function of M_1 from that of M_2.

2. (20pts.) Informally, but clearly, describe how a 3-counter machine could recognize {0^n1^n2^n | n >= 1}, that is the set of strings with some number of 0's followed by equal numbers of 1's and then 2's. Remember that a counter machine, like a PDA, can read its input only once, from left to right. You could, for instance, count the number of 0's on one counter, but then you would have to match that count against both the 1's and the 2's, without going back on the input to recount the 0's. Thus, you'll have to find a better strategy than that.

3. (20pts.) Consider the property P of languages: ``has at most 100 strings.''

(a)
Is P a decidable property of Turing machines (i.e., is the set of codes for TM's whose language has property P decidable)? Prove your answer. Note: there is a very simple answer and justification for this part.

(b)

4. (20pts.) Do the following instances of PCP have a solution. Justify your answers in each case.

(a)
Indexw_ix_i
1111
21110
30111

(b)
Indexw_ix_i
1111
211100
30111

5. (20pts.) Call a CFG superambiguous if it generates at least one string that has at least 100 different leftmost derivations. Prove that it is undecidable whether a CFG is superambiguous. Hint: Show how to perform a reduction from the problem of ambiguity to the problem of superambiguity. That is, given a CFG G, turn it into another CFG H such that H is superambiguous if and only if G is ambiguous.