CS154 Assignment #6 and CS154N Asssignment #2
Due Monday, March 6, 2000, 3:15PM
-
(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.
-
(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.
-
(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)
-
Is P recursively enumerable?
Prove your answer.
-
(20pts.)
Do the following instances of PCP have a solution.
Justify your answers in each case.
- (a)
-
| Index | w_i | x_i |
|---|
| 1 | 1 | 11 |
| 2 | 11 | 10 |
| 3 | 011 | 1 |
- (b)
-
| Index | w_i | x_i |
|---|
| 1 | 1 | 11 |
| 2 | 11 | 100 |
| 3 | 011 | 1 |
-
(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.