Abstract

We define an automata-theoretic counterpart of grammars based on the Lambek-calculus L, a prominent formalism in computational linguistics. While the usual push-down automaton has the same weak generative power as the L-based grammars , there is no direct relationship between the computations of a PDA for some language L and the derivations of an L-based grammar for L. In the Lambek-automaton, on the other hand, there is a tight relation between automaton computations and grammar derivations. The automaton exhibits a novel mode of operation, using hypothetical steps, directly inspired by the hypothetical reasoning embodied by L