Texts and Monographs in Computer Science Editor David Gries Advisory Board \ F. L. Bauer S. D. Brookes C. E. Leiserson F. B. Schneider M. Sipser The AKM Series in Theoretical Computer Science A Subseries of Texts and Monographs in Computer Science A Basis for Theoretical Computer Science by M. A. Arbib, A. J. Kfoury, and R. N. Moll A Programming Approach to Computability by A. J. Kfoury, R. N. Moll, and M. A. Arbib An Introduction to Formal Language Theory by R. N. Moll, M. A. Arbib, and A. J. Kfoury Algebraic Approaches to Program Semantics by E. G. Manes and M. A. Arbib Robert N. Moll Michael A. Arbib A. J. Kfoury An Introduction to Formal Language Theory With Contributions by James Pustejovsky With 61 Illustrations Spring-Verlag New York Berlin Heidelberg London Paris Tokyo Robert N. Moll Michael A. Arbib University of Massachusetts University of Southern California at Amherst Los Angeles, CA 90089-0782 Amherst, MA 01003 USA USA A. J. Kfoury James Pustejovsky (Contributor) Boston University Brandeis University Boston, MA 02215 Waltham, MA 02254 USA USA Series Editor David Gries Department of Computer Science Cornell University Upson Hall Ithaca, NY 14853 USA Library of Congress Cataloging-in-Publication Data Moll, Robert N. An introduction to formal language theory. (Texts and monographs in computer science) Bibliography: p. 1. Programming languages (Electronic computers) 2. Formallanguages. I. Arbib, Michael A. II. Kfoury, A. J. III. Title. IV. Series. QA76.7.M65 1988 005.13 88-2025 © 1988 by Springer-Verlag New York Inc. Softcover reprint of the hardcover lst edition 1988 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Verlag, 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, com- puter software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Typeset by Asco Trade Typesetting Ltd., Hong Kong. 98765 4 3 2 1 ISBN-13: 978-1-4613-9597-3 e-ISBN-13: 978-1-4613-9595-9 DOl: 10.1007/978-1-4613-9595-9 In Memory of James Peter Thorne Linguist and Lover of Language Preface The study of formal languages and of related families of automata has long been at the core of theoretical computer science. Until recently, the main reasons for this centrality were connected with the specification and analy- sis of programming languages, which led naturally to the following ques- tions. How might a grammar be written for such a language? How could we check whether a text were or were not a well-formed program generated by that grammar? How could we parse a program to provide the structural analysis needed by a compiler? How could we check for ambiguity to en- sure that a program has a unique analysis to be passed to the computer? This focus on programming languages has now been broadened by the in- creasing concern of computer scientists with designing interfaces which allow humans to communicate with computers in a natural language, at least concerning problems in some well-delimited domain of discourse. The necessary work in computational linguistics draws on studies both within linguistics (the analysis of human languages) and within artificial intelligence. The present volume is the first textbook to combine the topics of formal language theory traditionally taught in the context of program- ming languages with an introduction to issues in computational linguistics. It is one of a series, The AKM Series in Theoretical Computer Science, designed to make key mathematical developments in computer science readily accessible to undergraduate and beginning graduate students. The book is essentially self-contained-what little background is required may be found in the AKM volume A Basis for Theoretical Computer Science. After an overview of the entire territory in Chapter 1, we present the "standard material" for a computer science course in formal language the- ory in Chapters 2 through 5-the various families of languages: regular, viii Preface context-free, context-sensitive, and arbitrary phrase structure languages; and the corresponding families of automata: finite-state, push-down, linear bounded, and Turing machines. Along the way we introduce a number of related topics, including closure properties, normal forms, nondeter- minism, basic parsing algorithms, and the theory of computability and undecidability (developed at greater length in the AKM volume A Pro- gramming Approach to Computability). Much of the American work on theoretical computer science has empha- sized combinatorial techniques, but there is a growing appreciation of the role of algebraic techniques in analyzing the syntax and semantics of pro- gramming languages (see the AKM volume Algebraic Approaches to Pro- gram Semantics). We introduce the reader to this area by devoting Chapter 6 to the fixed point approach to the analysis of context-free languages. We then devote Chapter 7 to advanced topics in parsing, which provide the bridge from formal language theory to computer language design, namely the study of LL and LR grammars. We believe that readers will find this an unusually accessible, yet precise, introduction to the subject. Finally, Chapters 8 and 9 present our introduction to the formal theory of natural languages. We show how an analysis of properties of English sentences (e.g., the relation of active to passive sentences or the need to mark agreement between subject and verb) led to the development of Chomsky's theory of transformational grammar. We then develop alterna- tive schemes for representing natural language, e.g., augmented transition networks (ATNs) and generalized phrase structure grammar (GPSG), and offer some formal analysis of their properties. The first draft of the last two chapters was prepared by James Pustejov- sky, who then collaborated with the authors in producing the version that we now place before you. We are most grateful to him for sharing with us, and thus with the reader, his expertise in both transformational grammar and computational linguistics. With his contributions, we reiterate that the study of languages by computer scientists can no longer be restricted to programming languages, but must include the study of natural languages, as artificial intelligence and the design of natural language interfaces be- come ever more important topics within computer science. The book grew out of our teaching of classes at the University of Massachusetts at Amherst and at Boston University over several years. We thank our students for their helpful feedback as we developed this material, and we thank Darlene Freedman, Rae Ann Weymouth, and Susan Parker for their help in typing the manuscript. October 1987 R.N.MoLL M. A. ARBIB A. J. KFOURY Contents Preface vii CHAPTER 1 Introduction 1.1 The First Language 1 1.2 Grammers and Languages 3 1.3 Context-Free and Context-Sensitive Languages 8 1.4 Programs, Languages, and Parsing 13 1.5 Context-Free Grammars and Natural Language 20 CHAPTER 2 Grammars and Machines 2.1 The Chomsky Hierarchy 22 2.2 Closure Properties 28 2.3 Regular and Finite-State Languages 34 CHAPTER 3 Push-Down Automata and Context-Free Grammars 3.1 Push-Down Automata 46 3.2 Normal Forms for Context-Free Grammars 54 3.3 The Equivalence Theorem 59 CHAPTER 4 Parsing, Part 1 4.1 The Cocke-Kasami-Younger Algorithm 64 4.2 Earley's Algorithm 72 x Contents CHAPTER 5 Turing Machines and Language Theory 5.1 Turing Machines 81 5.2 The Universal Turing Machine 85 5.3 Nondeterministic Turing Machines and Linear Bounded Automata 93 5.4 The Halting Problem and Undecidability 100 CHAPTER 6 Fixed Point Principles in Language Theory 6.1 Partial Orders and Fixed Points 109 6.2 Fixed Point Theory and Context-Free Languages 117 CHAPTER 7 Parsing, Part II 7.1 Top-Down Parsing and LL Grammars 127 7.2 Bottom-Up Parsing and LR Grammars 132 CHAPTER 8 The Formal Description of Natural Languages 8.1 The Aims of Linguistic Theory 145 8.2 The Generative Power of Natural Languages 161 8.3 Augmented Transition Networks 167 CHAPTER 9 Recent Approaches to Linguistic Theory 9.1 Beyond Unrestricted Phrase Structure Formalisms 174 9.2 Generalized Phrase Structure Grammars 182 9.3 Government and Binding Theory 188 References for Chapters 8 and 9 196 Symbol Index 197 Author Index 199 Subject Index 200 CHAPTER 1 Introduction 1.1 The First Language 1.2 Grammars and Languages 1.3 Context-Free and Context-Sensitive Languages 1.4 Programs, Languages, and Parsing 1.5 Context-Free Grammars and Natural Language 1.1 The First Language The modern theory offormallanguages stems from two sources: the American linguist Noam Chomsky's attempt in the 1950's to give a precise characteriza- tion of the structure of natural languages, such as English and French, ac- cording to formal mathematical rules, and the development of a formal specification for the computer language ALGOL 60. Chomsky's work sought to describe the syntax of natural language according to simple replacement rules and transformations. Chomsky considered a number of possible rule restrictions, the most promising of which gave rise to a class of grammars known as context-free grammars, which generated the "deep structures" upon which transformations operate. Context-free grammars and the class of context-free languages they generate will be the principal object of study in this volume. This is primarily because the development of ALGOL 60, which soon followed Chomsky's attempted characterization of natural language, demonstrated that context-free grammars are reasonably adequate systems for describing the basic syntax of many programming languages. We will also study some issues in natural language processing, given the increasing im- portance of computational linguistics in the construction of natural language interfaces. As a first example of a context-free language, we examine the "language" of matched parentheses. This language plays a fundamental role in computer science as a notation for marking "scope" in mathematical expressions and programming languages. In the latter case, begin and end are often used instead of "(" and ")".