Page 215

		9.37 Definition Let  be a nonempty finite multiset of grammars. Then the grammar majority(Â) is defined to be a grammar such that .

		Clearly, majority(Â) can be defined using the s-m-n theorem (Theorem 2.1). Intuitively, majority(Â) is a grammar for a language that consists of all such elements that are enumerated by a majority of grammars in Â. Below, whenever we use a set as an argument to majority we assume the argument to be a multiset.

		Proof (of Proposition 9.36): Let j and k be as given in the hypothesis of the proposition. Let by a team consisting of scientists M1, M2, . . . , Mk. We then describe a scientist M that .

		For a finite sequence  s  and a scientist M', define

		Intuitively, conv(M',  s ) is the length of the longest subsequence of a where M' conjectures a hypothesis distinct from the one it conjectures on  s .

		Let , , . . ., be a permutation of l, 2, . . . , k, such that, for ,

		Note: ''<" here refers to ordering on pairs: (k0, l0) < (k1, l1) just in case either k0 < k1 or else k0 = kl and l0 < l1.

		For each  s , define .

		To complete the proof it must be shown that if the team consisting of scientists M1, M2, . . . , Mk , then M TxtEx-identifies L. This is the subject of Exercise 9-8.

		Proposition 9.38 below says that the collections of languages that can be identified by a team with success ratio (that is, at least two-thirds of the members in the team are required to be successful) are the same as those collections of languages that can be identified by a team of 3 scientists, at least 2 of which are required to be successful.

		9.38 Proposition For each j > 0, .

		Proof: Let j be as given in the hypothesis of the proposition. Suppose a team consisting of scientists M1, . . . , M3j . We then describe scientists , , and such that the team consisting of , , and witnesses .