M.Sc Thesis | |

M.Sc Student | Veksler Tatyana |
---|---|

Subject | Automata and Type-Logical Grammars |

Department | Department 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**.