Transductions and Context-Free LanguagesThis 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. |
Other editions - View all
Common terms and phrases
a₁ algebraic grammar algebraic languages alphabetic morphism Assume b₁ Clearly closed under substitution closure operator Consequently consider contains context-free grammar context-free languages Conversely Corollary counter languages D₁ defined dom(a Dyck language Example Exercise exists family of languages free monoid full AFL grammar G grammatical with respect Greibach h₁ idempotent implies incomparable independent system integer iteration lemma iterative pairs left factor letter linear grammar linear languages M-substitution M₁ monoid Nivat's nondegenerated P₁ partial function principal cone Proof Proposition prove quasi-rational Rat(M Rat(X rational cone rational function rational language rational relation rational subset rational transduction Rec(M recognizable regular language respect to G right factor right sequential Rocl S₂ Section Seiten sequential transducer strict submonoid subsequential system of iterative Theorem u₁ unambiguous v₁ w₁ w₂ word x₁