M.Sc Thesis

M.Sc StudentVeksler Tatyana
SubjectAutomata and Type-Logical Grammars
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Nissim Francez


One of the frameworks by which computational linguistics suggests to specify natural language syntax is Type-Logical Grammars. Type-logical grammars are not rewriting grammars. They are based on a category system and a grammatical process of derivation, reducing sequences of categories until a specific initial category is obtained. In a type-logical grammar each terminal is given a finite set of categories, and there is a collection of universal logical rules, which do not depend on a specific language. Therefore, the lexicon, assigning (finite) sets of categories to terminals, plays a major role in this kind of grammars.

One basic logical system for obtaining deductions in these grammars is the Ajdukiewicz-Bar-Hillel calculus (AB). Another one, the (associative) Lambek calculus (L), which is of our main interest in this paper, is an extension of the AB-calculus by arrow introduction rules, which embody the hypothetical reasoning capacity of L.

The goal of this thesis is to define an automaton that accepts the languages accepted by L-based grammars. L-based grammars were proved by Pentus to be equal in their weak generative power to context-free grammars. Since context-free grammars may be efficiently accepted by means of an item pushdown automaton, it is possible to translate an L-based grammar into a context free grammar and then accept it, using an item pushdown automaton corresponding to the resulting context-free grammar. However, the resulting automaton will be only remotely connected to the original L-based grammar. Moreover, the translation of an L-based grammar to a context-free grammar is not efficient.

In this work we define an automaton for accepting L-based languages, which is efficiently built directly from the type-logical grammar. We prove that for every L-based grammar G there is a Lambek automaton MG, such that L(MG)=L(G) and vice versa, for every Lambek automaton M there is an L-based grammar GM, such that L(GM)=L(M). Furthermore, in both cases runs of the automata are tightly related to derivations in the grammars. Thus, Lambek automata embody the hypothetical reasoning of L.