Teubner Studienbücher Informatik J. Berste! Transductions and Context-Free Languages LeiHäden der angewandten Mathematik und Mechanik LAMM Unter Mitwirkung von Prof. Dr. E. Becker, Darmstadt Prof. Dr. G. Hotz, Saarbrücken Prof. Dr. P. Kali, Zürich Prof. Dr. K. Magnus, München Prof. Dr. E. Meister, Darmstadt Prof. Dr. Dr. h. c. F. K. G. Odqvist, Stockholm Prof. Dr. Dr. h. c. Dr. h. c. Dr. h. c. E. Stiefelt herausgegeben von Prof. Dr. Dr. h. c. H. Görtler, Freiburg Band 38 Die Lehrbücher dieser Reihe sind einerseits allen mathematischen Theo rien und Methoden von grundsätzlicher Bedeutung für die Anwendung der Mathematik gewidmet; andererseits werden auch die Anwendungs gebiete selbst behandelt. Die Bände der Reihe sollen dem Ingenieur und Naturwissenschaftler die Kenntnis der mathematischen Methoden, dem Mathematiker die Kenntnisse der Anwendungsgebiete seiner Wissen schaft zugänglich machen. Die Werke sind für die angehenden Industrie und Wirtschaftsmathematiker, Ingenieure und Naturwissenschaftler be stimmt, darüber hinaus aber sollen sie den im praktischen Beruf Tätigen zur Fortbildung im Zuge der fortschreitenden Wissenschaft dienen. Transductions and Context-Free Languages By Dr. Jean Berste! Professor at the Universite P. et M. Curfe, Paris With 32 figuras, 158 exercises and numerous examples Ef3 Springer Fachmedien Wiesbaden GmbH 1979 Prof. Jean Berste) Born in 1941 at Nimes (France). From 1961 to 1966 studies in mathematics at the University of Paris. 1967 These de troisieme cycle, 1972 These d'Etat at the University of Paris. From 1970 to 1972 Charge d'Enseignement at the University of Strasbourg. Since 1972, Maitre de Conference, then Profes sor at the Institut de Programmation, University of Paris VI Durlog the Summer Semester 1976 on leave at the University of Saarbrücken. Activity: Mathematicol and Theoretical Compu ter Science. CIP-Kurztitelaufnahme der Deutschen Bibliothek Rentel, Jean: Transductions and context-free languages I by Jean Berste!. (Leitfäden der angewandten Mathematik und Mechanik ; Bd. 38) (Teubner Studienbücher : Informatik) ISBN 978-3-519-02340-1 ISBN 978-3-663-09367-1 (eBook) DOI 10.1007/978-3-663-09367-1 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproductions byphotocop ying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher. © Springer Fachmedien Wiesbaden 1979 Ursprünglich erschienen bei B.G. Teubner, Stuttgart 1979 Softcover reprint of the bardeover 1st edition 1979 Setting: The Universities Press (Belfast) Ltd., Belfast Cover design: W. Koch, Sindelfingen Preface This book presents a theory of formal languages with main emphasis on rational transductions and their use for the classification of context-free lan guages. The Ievel of presentation corresponds to that of beginning graduate or advanced undergraduate work. Prerequisites for this book are covered by a "standard" first-semester coursein formallanguages and automata theory: e.g. a knowledge of Chapters 1-3 of Ginsburg [1966], or Chapters 3-4 of Hopcroft and Ullman [1971], or Chapter 2 of Salomaa [1973], or Chap ters 2 and 4 of Becker and Walter [1977] would suffice. The book is self-contained in the sense that complete proofs are given for all theorems stated, except for some basic results explicitly summarized at the beginning of the text. Chapter IV and Chapters V-VIII are independent from each other. The subject matter is divided into two preliminary and six main chapters. The initial two chapters contain a general survey of the "classical" theory of regular and context-free languages with a detailed description of several special languages. Chapter III deals with the general theory of rational transductions, treated in an algebraic fashion along the lines of Eilenberg, and which will be used systematically in subsequent chapters. Chapter N is concerned with the important special case of rational functions, and gives a full treatment of the latest developments, including subsequential transductions, unambiguous trans ducers and decision problems. The study of families of languages (in the sense of Ginsburg) begins with Chapter V. There, the structures of "rational cone" and "full AFL" are introduced, and some general results are established. The chapter ends with the treatment of several examples of cones of linear languages. Chapter VI contains a theory of operators on families of languages, setting up an algebraic framework for transformation and comparison of families of languages. Other general results on cones and full AFLs are easily derived from a series of inequalities involving only Operators. Chapter VII is concerned with the study of principal cones and full AFLs, that is families generated by one language only. Main interest is in subcones of the context-free languages. First, several languages are proved to generate the entire cone of context-free languages. Then S. Greibach's "Syntactic Lemma" is proved and used to exhibit nonprin cipal cones. A detailed study of two important families follows, namely the family of one counter and the family of quasi-rational (nonexpansive, derivation-bounded · · ·) languages. Chapter VIII presents a general method (due to Boassan and Beauquier) for proving strict containment or incompara- 6 Preface bility of cones of context-free languages, using iterative pairs and systems of iterative pairs. This method yields easy proofs of the existence of several wellknown and of new hierarchies of cones of context-free languages, showing thus the intirnate connection between iterative pairs and the structure of context-free languages. Main interest is in languages rather than in grammars or in acceptors. Indeed, a language (even a context-free one) exists independently from the grammars generating it, and a great number of context-free languages can be described by a combinatorial or an algebraic property, without any reference to a grammar. Moreover, grammatical characterizations of classes of languages usually require just the existence of one grammar of some special type. Thus to prove that a given language is not in the family, one must show that all grammars generating it violate some property. This is usually a very delicate proof. Finally there are results which are proved by the method of iterative pairs and which cannot be proved-up to now-by considering only grammars. Rational cones are treated in greater detail than full AFLs. They are indeed in a natural relationship with rational transductions; further full AFLs are a secondary structure in the sense that any full AFL is the rational closure of some cone. Since we are mainly concerned with context-free languages, a description of AFLs and "trios" (in Opposition to full AFLs and rational cones) seemed unnecessary, all the more as some fundamental results such as the Syntactic Lemma are still lacking for these families. The notes from which this book derives were used in courses at the University of Paris and at the University of Saarbrücken. I want to thank Professor G. Hotz for the opportunity he gave me to stay with the Institut für angewandte Mathematik and Informatik, and for his encouragements to write this book. I am grateful to the following people for useful discussions or comments con cerning various parts of the text: J. M. Autebert, J. Beauquier, Ch. Choffrut, G. Cousineau, K. Estenfeld, R. Linder, M. Nivat, D. Perrin, J. F. Perrot, J. Sakarovitch, M. Soria, M. Stadel, H. Walter. I am deeply indebted to M. P. Schützenherger for his constant interest in this book and for many fruitful discussions. Special thanks are due to L. Boasson whose comments have been of an invaluable help in the preparation of many sections of this book. I want to thank also J. Messerschmidt for his careful reading of the manuscript and for many pertinent comments, and Ch. Reutenauer for checking the galley proofs. I owe a special debt to my wife for her active contribution at each step of the preparation of the book, and to Bruno and Clara for their indulgence. Paris, Spring 1978 J. Berste! Contents I Preliminaries 1.1 Some Notations . 9 1.2 Monoids, Free Monoids . 9 1.3 Morphisms, Congruences. 12 1.4 Finite Automata, Regular Languages 15 II Context-Free Languages 11.1 Grammars, Languages, Equations 22 11.2 Closure Properties, Iteration 31 11.3 Dyck Languages . . . 35 11.4 Two Special Languages . 47 III Rational Transductions 111.1 Recognizable Sets 51 111.2 Rational Sets . . 55 111.3 Rational Relations 61 111.4 Rational Transductions. 65 111.5 Examples . . . . . 72 111.6 Transducers. . . . . 77 111.7 Matrix Representations. 80 111.8 Decision Problems 87 IV Rational Functions IV.l Rational Functions 92 IV.2 Sequential Transductions . . 96 IV.3 The Cross-Section Theorem . 111 IV.4 Unambiguous Transducers 114 IV.5 Bimachines. . . . 123 IV.6 A Decidable Property 128 V FarnDies of Languages V.1 Definition. . . . 134 V.2 Rational Equivalence, Rational Cones. 135 V.3 Rationally Closed Families. 138 V.4 Full AFLs . . . . . . . . . . 141 8 Contents V.5 Substitution . 145 V.6 Example: The Cone of Linear Languages 150 V.7 Examples of Incomparable Languages. 156 VI Operators VI.l Operators . . . . . 162 Vl.2 Examples of Operators 164 Vl.3 Closure Operators . . 166 VI.4 Subcommutative Relations 171 Vl.5 Marked Substitution 177 VII Generators VII.1 Generators of the Context-Free Languages 185 VII.2 The Syntactic Lemma. . . 194 VI1.3 Substitution Oosure . . . 197 VII.4 One Counter Languages . · 201 VII.5 Quasi-Rational Languages 208 VID Iterative Pairs VIII.1 Types of Iterative Pairs . 219 VIII.2 Grammatical Pairs 223 VIII.3 Transfer of Iterative Pairs . 227 VIII.4 Systems of Iterative Pairs 232 VII1.5 Grammatical Systems 237 VIII.6 Transfer of Systems . . 246 VIII. 7 Applications. . . . . 251 IX Open Problems, Further Developments 265 Bibliography . 268 List of Symbols 274 Index . ... 275 I Preliminaries This chapter is a short review of some basic concepts used in the sequel. Its aim is to agree on notations and terminology. We first consider monoids, especially free monoids, and morphisms. Then a collection of definitions and results is given, dealing with finite automata and regular languages. 1.1 Some Notations N ={0, 1, 2, ....} is the set of nonnegative integers. Ll' ={· · · -2, -1, 0, 1, ...} is the set of integers. Let E be a set. Then Card(E) is the number of its elements. The empty set is denoted by fZ). If A, B are subsets of E, then we write A c B iff x E A :::} x E B, and A ~ B iff A c B and A ~ B. Further I A \B ={xEE xEA and x$B}. A singleton is a subset of E consisting of just one element. If no confusion can arise, we shall not distinguish elements of E from singletons. The set of all subsets of E, i.e. the powerset of E, is denoted by ~(E) or 2E. With the preceding convention, E c ~(E). The d o m a in dom( a) of a partial function a : E--+ F is the set of elements x in E for which a(x) is defined. a can be viewed as a (total) function from E into ~(F), and with the convention Fe \lHF), as a total function from E into FU{fZ)}. Then dom(a)={xEEia(x)~fZ)}. 1.2 Monoids, Free Monoids A semigroup consists of a set M and a binary operation on M, usually denoted by multiplication, and which is postulated tobe associative: For any m" m2, m3EM, m1(m2m3)=(m1m2)m3• A neutral element or a unit is an element 1M E M (also noted 1 for short) such that 1Mm = m 1M= m for all m E M. A semi-group which has a neutral element is a mono i d. The neutral element of a monoid is unique. lndeed, if 1' is another neutral element then 1'=11'=1. Given two subsets A, B of a monoid M, the product AB is defined by AB ={cEM l3a EA, 3bEB :c =ab}. (2.1)