purely formal expressions freely generated from the primitive types; any semantics will be added later. Some authors assume a fixed infinite set of primitive types used by all grammars, but by making the primitive types part of the grammar, the whole construction is kept finite. A basic categorial grammar is a tuple where is a finite set of symbols, is a finite set of primitive types, and . The relation is the lexicon, which relates types to symbols . Since the lexicon is finite, it can be specified by listing a set of pairs like . Such a grammar for English might have three basic types , assigning count nouns the type , complete noun phrases the type , and sentences the type . Then an adjective could have the type , because if it is followed by a noun then the whole phrase is a noun. Similarly, a determiner has the type , because it forms a complete noun phrase when followed by a noun. Intransitive verbs have the type , and transitive verbs the type . Then a string of words is a sentence if it has overall type . For example, take the string "the bad boy made that mess". Now "the" and "that" are determiners, "boy" and "mess" are nouns, "bad" is an adjective, and "made" is a transitive verb, so the lexicon is {, , , , , }. and the sequence of types in the string is now find functions and appropriate arguments and reduce them according to the two inference rules and : The fact that the result is means that the string is a sentence, while the sequence of reductions shows that it can be parsed as ((the (bad boy)) (made (that mess))). Categorial grammars of this form (having only function application rules) are equivalent in generative capacity to context-free grammars and are thus often considered inadequate for theories of natural language syntax. Unlike CFGs, categorial grammars are lexicalized, meaning that only a small number of (mostly language-independent) rules are employed, and all other syntactic phenomena derive from the lexical entries of specific words. Another appealing aspect of categorial grammars is that it is often easy to assign them a compositional semantics, by first assigning interpretation types to all the basic categories, and then associating all the derived categories with appropriate function types. The interpretation of any constituent is then simply the