## Paper: Lambek grammars are context free (at LICS 1993)

**Mati Pentus**

### Abstract

Basic categorial grammars are the context-free ones. Another kind of categorial grammars was introduced by J. Lambek (1958). These grammars are based on a syntactic calculus, known as the Lambek calculus. Chomsky (1963) conjectured that these grammars are also equivalent to context-free ones. Every basic categorial grammar (and thus every context-free grammar) is equivalent to a Lambek grammar. Conversely, some special kinds of Lambek grammars are context-free. These grammars use weakly unidirectional types, or types of order at most two. The main result of this paper says that Lambek grammars generate only context-free languages. Thus they are equivalent to context-free grammars and also to basic categorial grammars. The Chomsky conjecture, that all languages recognized by the Lambek calculus are context-free, is thus proved

### BibTeX

@InProceedings{Pentus-Lambekgrammarsareco, author = {Mati Pentus}, title = {Lambek grammars are context free}, booktitle = {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)}, year = {1993}, month = {June}, pages = {429--433}, location = {Montreal, Canada}, publisher = {IEEE Computer Society Press} }