CIDEC ÜIK |
Estonian Winter Schools in Computer Science Eesti arvutiteaduse talvekoolid |
EWSCS 2000 EATTK 2000 |

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/

18/02/2000 monika@cs.ioc.ee