Abstract

We prove that a formal language without the empty word is context-free if and only if it is generated by some L-grammar, where L is the Lambek calculus with one division and one primitive type. To do that, we use a substitution of types which reduces derivability in L to derivability in L. We also prove that a formal language is context-free if and only if it is generated by some L*-grammar is a variant of L that allows empty premises). To do that, we introduce a construction which adds the empty word to languages generated by a special subclass of L*-grammars and then use the same substitution as for L