Page 190

		F is said to N*Lang-identify (written: ) just in case given any *-noisy text for L, F converges to an index for L. The class N*Lang is . Prove the following generalization of Theorem 3.22 from Chapter 3.

		(a) Let F N*Lang-identify . Then, for every finite , there is such that , WF( s ) = L, and for all , if , then

		(b) Let F N*Lang-identify . Show that for every there is some such that , and for every , if , then .

		8-4 Let . Show that .

		8-5 Prove the following.

		(a) Let L, be such that and . Then, both L - L' and L' - L are infinite.

		(b) Let be such that whenever L, and , then both L - L' and L' - L are infinite. Then, .

		8-6 Define In*Lang and Im*Lang analogously to the definition of N*Lang in Exercise 8-3. Prove the following generalizations of Theorem 3.22 from Chapter 3.

		(a) Let F In*Lang-identify . Then, for every finite there is such that , WF( s ) = L, and for all , if , then .

		(b) Let F Im*Lang-identify . Then, for every finite variant L' of L there is such that , WF( s ) = L and for all , if , then .

		8-7 Prove .

		8-8 Define N*Func and In*Func analogously to N*Lang and In*Lang. Prove N*Func = In*Func.

		8-9 Prove the following.