Dr. Mati Pentus

CORRESPONDENCE BETWEEN LAMBEK GRAMMARS AND CONTEXT-FREE GRAMMARS

Abstract

The mathematical theory of formal languages was founded by N. Chomsky in 1950s. A formal language is a (usually infinite) set of finite words over a finite alphabet. It is generally believed that the best approximation of natural languages and programming languages in the Chomsky hierarchy is provided by the class of context-free languages.

In late 1950s J. Lambek proposed an alternative logico-algebraic approach to formal language specification (as opposed to Chomsky's recursion-theoretic approach). The Lambek calculus describes the properties of formal languages via defining relations of three basic operations on languages: multiplication, left and right division.

It is easy to show that every context-free language is defined by some Lambek grammar. In early 1960s N. Chomsky conjectured that the converse holds too. We sketch the proof of this conjecture.

Contact information:
Department of Mathematical Logic and Theory of Algorithms
Faculty of Mechanics and Mathematics
Moscow State University
Vorob'evy Gory, Moscow, 119899 RUSSIA
Tel/fax: + 7 - 095 - 939 30 31

EMAIL: pentus@lpcs.math.msu.ru
WWW: http://markov.math.msu.ru/~pentus/