Page 141

		6.24 Proposition (Case and Lynes [33])

		(a) .

		(b) For each , .

		Proof: We prove part (b). A proof of part (a) can be worked out by employing an analog of the locking sequence lemma (Theorem 3.22) for TxtBca-identification (see Exercise 6-9).

		Suppose scientist . We construct a scientist .

		By the s-m-n theorem (Theorem 2.1), for each  s , there is an index p s  such that

		,

		where in the second part if has fewer than m elements, we just take . For each  s , we take M'( s ) = p s .

		Let T be a text for and let p be the index to which M converges on T. Hence, Wp =2m L. Let n0 be such that, for all ,

		(a) M(T[n] = p,

		(b) and , and

		(c) .

		Clearly, such an n0 exists. Note that, for each n > n0, M' patches all the errors of omission of M.

		Now fix an . Let M(T[n]) = p. Consider the following two cases:

		Case 1: . That is, the number of mistakes of commission in . Then, p[n] removes m of these mistakes of commission, errors.

		Case 2: card(Wp - L) = m' and m' < m. That is, the number m' of mistakes of commission in p is < m. Then, pT[n] removes all these errors of commission, but potentially creates up to m - m' new errors of omission. However, this number, m - m', is still .

		In both cases, errors, hence M' TxtBcm-identifies .

		§6.2.3 Vacillatory Language Identification

		Recall the vacillatory criterion of success for functions introduced in Section 6.1.4. To be successful in the vacillatory sense, the learner's conjectures must eventually remain