





Technical Report: DCC20011Generating Normal Inhabitants of Types with a Common StructureSabine Broda and Luís DamasR. do Campo Alegre 823, 4150180 Porto, Portugal Phone: 351 22 6078830, Fax: 351 22 6003654 Email: {sbb,luis}@ncc.up.pt} AbstractIn 1996 Takahashi et al. showed that it is possible to describe the set of normal inhabitants of a given type $\tau$, in the standard simple type system, using an infinitary extension of the concept of contextfree grammar, which allows for an infinite number of nonterminal symbols as well as production rules. The set of normal inhabitants of $\tau$ corresponds then to the set of terms generated by this, possibly infinitary, grammar plus all terms obtained from those by $\eta$reduction. In this paper we show that the set of normal inhabitants of a type $\tau$ can in fact be described using a standard (finite) contextfree grammar, and more interestingly that the sets of normal inhabitants of all types with a same structure are described by contextfree grammars which share one unique underlying structure. The definition of a common scheme for these grammars, which depends uniquely on the given type structure, is based on an alternative representation for types, introduced in 2000 (BrodaDamasWollic2000), which gives us a better insight on the nature of a type's structure and its relation to the structure of the set of its normal inhabitants. 

