|
|
|
|
|
|
and  . Finally, let |
|
|
|
|
|
|
|
|
Clearly,  . Also, since grammars for L1 and L2 are valid additional information of types Uap1 and Uacp1 respectively, we have that  . Suppose by way of contradiction that M TxtExk-identifies  . It is, then, easy to convert M to M' such that M' TxtExk-identifies  . But this is not true as implied by Exercise 6-3. Thus, no such M can exist. |
|
|
|
|
|
|
|
|
We leave the proof of the following as an exercise. |
|
|
|
|
|
|
|
|
10.46 Proposition  |
|
|
|
|
|
|
|
|
The next proposition illustrates the power of Uacp-type negative additional information over Acp-type negative additional information. More precisely, there are collections of languages that can be identified in the presence of some Uacp-type additional information of nonzero density, but cannot be identified in the presence of the best possible Acp-type negative additional information, even if the scientist is also given the best possible positive additional information (Uap-type density 1) and is only required to converge to a grammar for a finite variant of the language. The proof of the proposition is treated in Exercise 10-19. |
|
|
|
|
|
|
|
|
10.47 Proposition For all d > 0,  |
|
|
|
|
|
|
|
|
A similar result below illustrates the power of Uap-type positive additional information over Ap-type positive additional information. That is, there are collections of languages that can be identified in the presence of some Uap-type additional information of nonzero density, but cannot be identified in the presence of the best possible Ap-type positive additional information, even if the scientist is also given the best possible negative additional information (Uacp-type density 1) and is only required to converge to a grammar for a finite variant of the language. See Jain and Sharma [85] for the proof. |
|
|
|
|
|
|
|
|
10.48 Proposition For all d > 0,  |
|
|
|
|
|
|
|
|
The next result illustrates the power of Ap-type positive additional information over lower density Uap-type positive additional information. More precisely, if d2 > d1, then there are collections of languages that can be identified in the presence of Ap-type positive additional information of density d2, but that cannot be identified in the |
|
|
|
|
