A Lambek Automaton

We define an automata-theoretic counterpart of (type-logical)grammars based on the (associative) Lambek-calculus L, a prominentformalism in computational linguistics. While the usual push-downautomaton (PDA) has the same weak generative power as the L-basedgrammars (Pentus, 1995), there is no direct relationship betweenthe computations of a PDA for some language L and the derivationsof an L-based grammar for L. In the Lambek-automaton, on theother hand, there is a tight relation (1-1) between automatoncomputations and grammar derivations. The automaton exhibitsa novel mode of operation, using hypothetical steps, directlyinspired by the hypothetical reasoning embodied by L.