The present work originates in a course given by the authors during the last few years in various university departments and institutions, among which we should like to mention: the Centre de Linguistique Quantitative of the Faculte des Sciences de Paris, created at the instance of the late Professor Favard; the Chaire d'Analyse Numerique of the Faculte des Sciences de Paris (Professor Rene de Possel), curriculum of Troisieme Cycle; the Chaire de Physique Mathematique of the University of Toulouse (Professor M. Laudet), for the degree DiplOme d'Etudes Approfondies in the section "Traitement de I'Information"; the department 1 of linguistics of the University of Pennsylvania (Professor Z. S. Harris); Institut de Programmation of the Faculte des Sciences de Paris for the troisieme niveau. the courses in the Written for purely didactic purposes, this Introduction to Formal Grammars makes no pretense to any scientific originality. Large portions of it have been borrowed from the fundamental and "classic" works cited in the bibliography, such as that of M. Davis, Computability and Unsolvability [9], and those of N. Chomsky, among others Formal Properties of Grammars [6]. Ineluctably, there are numerous borrowings made during a course, and the authors would like to acknowledge their debt to J. Pitrat for his lectures given in the Centre de Linguistique Quantitative mentioned above, and to M. Nivat for his work in connection 2 and transduction.

This volume contains the proceedings of the 15th Spring School of the LITP (Laboratoire d'Informatique ThA(c)orique et de Programmation, UniversitA(c) Paris VI-VII, CNRS) held from May 25 to 29, 1987 in Saint-Pierre d'OlA(c)ron. The meeting was organized by M. Borillo, M. Gross, M. Nivat and D. Perrin. The purpose of this yearly meeting is to present the state of the art in a specific topic which has gained considerable maturity. The proceedings of the last three Spring Schools have already been published in this series and deal with "Automata on Infinite Words" (LNCS 192), "Combinators and Functional Programming Languages" (LNCS 242) and "Automata Networks" (LNCS 316). The contributions gathered for the 1987 conference present a unique combination of automata theory on the one hand and natural language processing on the other hand. Both fields have strong historical links as exemplified by the works of Chomsky and Harris in Linguistics, the work of Backus and others in Computer Science and the work of SchA1/4tzenberger in Algebra. The methods described and discussed in the field of string processing and automata cover the traditional algorithms for string matching, data compression, sequence comparison and lexical analysis. The papers that deal more directly with natural language processing treat automated text generation, lexical analysis and formal representation.

In der traditionellen Sprachwissenschaft machte man eine wichtige Unterscheidung zwischen besonderer Grammatik und universaler Gram- matik, wobei sich die erste mit den idiosynkratischen Eigenschaften spezifischer Sprachen, die zweite mit den allgemeinen Merkmalen jeder menschlichen Sprache beschaftigt. In den letzten Jahren ist diese Un- terscheidung erneut in den Vordergrund der Forschung geruckt worden, und dieses erneute Interesse fiel mit dem Beginn ernsthafter Forschung auf einem Gebiet der mathematischen Linguistik zusammen, das man manch- mal algebraische Linguistik nennt, um es von statistischen Sprach- untersuchungen und vom Studium probilistischer Performanzmodelle zu unterscheiden. Das Zusammenfallen dieser Entwicklungen ist in mancher Hinsicht ganz naturlich. Algebraische Linguistik studiert die formalen Eigenschaften naturlicher Sprache, indem sie von spezifischen Realisie- rungen in einzelnen Sprachen abstrahiert. So definiert ist sie von der universalen Grammatik gar nicht zu unterscheiden, obwohl es in der Pra- xis eine Arbeitsteilung zwischen den starker empirisch orientierten Studien der universalen Grammatik und den streng mathematischen Studien der von der linguistischen Forschung vorgeschlagenen formalen Struktu- ren gegeben hat. Die Existenz dieser Teilung ist einerseits ein Zeichen fur den unausgereiften Stand der Forschung auf diesem Gebiet, anderer- seits eine Widerspiegelung der differierenden Motivationen und Inter- essen der einzelnen Forscher. Wenn die Teilung inhaltlich eingeschrankt werden kann, dann koennte eine echte Theorie der mathematischen Lingui- stik entstehen, die rein abstrakt die Klasse der von den Prinzipien der universalen Grammatik definierten Systeme untersucht - die Klasse moeg- licher menschlicher Sprachen.