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.

The verb 'pouvoir' is given short shrift in many of the usual sources used for translating French into English. It is noted there that this verb is triply ambiguous, and can mean 'can', 'may' or 'must'. But such information is too meagre to aid the user when faced with some of the complex tenses of 'pouvoir' followed by a variety of possible objects, or predicates. One case is when 'pouvoir' is followed by a perfect infinitive, with or without a negation. Such sequences generally lead to ponderous and inelegant translations for which alternative solutions must be found. These alternate solutions are discussed at length. A second relatively unnoticed and untreated difficulty is the use of the future 'pourra' or the future perfect 'aura pu' as a stylistic variation of the present 'peut' or the present perfect 'a pu'. This particular usage has no equivalent in English, and often traps the French learner into misunderstanding (and mistranslating) certain sentences. This particular stylistic variation is illustrated with many detailed examples showing that the future of 'pouvoir' is frequently translated by a present tense. Another difficulty is the almost totally ignored present and perfect participles 'pouvant' and 'ayant pu'. The problems in using them are never treated in any of the French grammars for English speakers or in any bilingual French-English dictionaries. This neglect of these participles may be due to a mistaken observation of them. They seem to present no problems: the one means 'being able' and the other 'having been able'. It is perhaps for this reason that no current French-English dictionary contains a single example of their use. Yet these two basic translations are not applicable to all the possible contexts in which these participles can appear. Sometimes it is 'pouvoir' as possibility that appears in 'pouvant', at other times it is 'pouvoir' as capability. The two translations above are largely insufficient to the task. The difficulties associated with the translation of each of the tenses of 'pouvoir' are discussed here in detail, something which cannot be found in the usual French grammars for English speakers. Various translations of certain tenses must be used for particular types of subject or object, and few of these are apparent to an English speaker learning French. Many of these variant translations require lengthy explanations, and they are given here. The French learner will surely find all this information of great use in understanding how 'pouvoir' is used in French, something which cannot be obtained from any of the usual grammar sources. The explanations of how its translation depends on the subject and the object which appear with it will also help him when he encounters new sentences with other subjects and objects of this verb.