The author covers the mainstream of formal language theory with preferential treatment of generative grammars. The first two chapters provide basic definitions concerning grammars and formal languages. The Chomsky classification of languages is presented, and the closure properties under regular operations of the language classes are discussed. Chapter3 deals with context-free grammars, including linear grammars. Transformations, which make the form of grammars simpler without changing the generated language, are studied. A section on regular expressions is included. Chapters4 and 5 concentrate on context-sensitive and unrestricted phrase structure grammars, respectively. The different natures of the classes of grammars and their relationships are discussed.

In the last five chapters, the author presents other aspects of formal languages. Chapter 6 considers automata as language-accepting devices and shows the correspondence of the hierarchy of automata to the Chomsky hierarchy of languages. Recursive and recursively enumerable languages and decidability problems are treated in chapter 7. The next chapter introduces complexity classes and determines the complexity of some problems concerning context-free languages. A chapter on parsing technique presents Earley’s algorithm for general context-free grammars and considers the subclasses of LL(k)-grammars and LR(k)-grammars. Finally, in chapter 10, the less common topic of derivation languages is discussed. This chapter on rewriting systems was written with J. M. Hart. All these topics are not presented in depth, but a basis for further studies is provided.

The textbook is intended for advanced undergraduate or graduate students. The main emphasis on generative grammars achieves a consistent presentation of formal languages. All other topics are added systematically to the presented material. Most of the chapters and sections start with an informal overview and mention other approaches to the topic or give references to further results. The author gives proofs of almost all theorems and assertions. References are given for the few proofs left out. Numerous examples illustrate the material. The exercises at the end of each section also concern understanding and application. A lot of hints to exercises are given, but the book contains no solutions. The material is presented clearly, and the reader needs little mathematical background. An appendix consists of a discussion of elementary set theory. The references, bibliographic remarks, and index are adequate.

The book is a slightly corrected republication of a work first published in 1983 [1]. For this reason, it contains no references to recent developments. Because of the classical content, however, the book serves its purpose as a student’s introductory textbook.