Formal Languages and Computation: Models and Their Applications gives a clear, comprehensive introduction to formal language theory and its applications in computer science. It covers all rudimental topics concerning formal languages and their models, especially grammars and automata, and sketches the basic ideas underlying the theory of computation, including computability, decidability, and computational complexity. Emphasizing the relationship between theory and application, the book describes many real-world applications, including computer science engineering techniques for language processing and their implementation.
Covers the theory of formal languages and their models, including all essential concepts and properties
Explains how language models underlie language processors
Pays a special attention to programming language analyzers, such as scanners and parsers, based on four language models―regular expressions, finite automata, context-free grammars, and pushdown automata
Discusses the mathematical notion of a Turing machine as a universally accepted formalization of the intuitive notion of a procedure
Reviews the general theory of computation, particularly computability and decidability
Considers problem-deciding algorithms in terms of their computational complexity measured according to time and space requirements
Points out that some problems are decidable in principle, but they are, in fact, intractable problems for absurdly high computational requirements of the algorithms that decide them
In short, this book represents a theoretically oriented treatment of formal languages and their models with a focus on their applications. It introduces all formalisms concerning them with enough rigors to make all results quite clear and valid. Every complicated mathematic

This book is designed to serve as a text for a one-semester introductory course in the theory of formal languages and computation. It covers all the traditional topics of this theory, such as automata, grammars, parsing, computability, decidability, computational complexity, and properties of formal languages. Special attention is paid to the fundamental models for formal languages and their appli-cations in computer science.
Subject
Formal language theory defines languages mathematically assets of sequences consisting of sym-bols. This definition encompasses almost all languages as they are commonly understood. Indeed, natural languages, such as English, are included in this definition. Of course, all artifcial lan-guages introduced by various scientific disciplines can be viewed as formal languages; perhaps most illustrative ly, every programming language represents a formal language in terms of this definition. It thus comes as no surprise that formal language theory, which represents a math-ematically systematized body of knowledge concerning formal languages, is important to all the scientific areas that make use of these languages to a certain extent.
The theory of formal languages represents the principal subject of this book. The text focuses its attention on the fundamental models for formal languages and their computation-related appli-cations in computer science, hence its title Formal Languages and Computation: Models and Their Applications.
Models
The strictly mathematical approach to languages necessitates introducing formal models that def ne them. Most models of this kind are underlain by rewriting systems, which are based on rules by which they repeatedly change sequences of symbols, called strings. Despite their broad variety, most of them can be classified into two basic categories—generative and accepting lan-guage models. Generative models, better known as grammars, define strings of their language, so their rewriting process generates them from a special start symbol. On the other hand, accepting models, better known as automata, define strings of their language by are writing process that starts from these strings and ends in a prescribed set of final strings.
Applications
The book presents applications of language models in both practical and theoretical computer science.
In practice, the text explains how appropriate language models underlie computer science engi-neering techniques used in language processors. It pays special attention to programming language analyzers based on four language models—regular expressions, finite automata, context-free grammars, and pushdown automata. More specifically, by using regular expressions and finite autom-at a, it builds up lexical analyzers, which recognize lexical units and verify that they are properly formed. Based on context-free grammars and pushdown automata, it creates syntax analyzers, which recognize syntactic structures in computer programs and verify that they are correctly written accord-ing to grammatical rules. That is, the text first explains how to specify the programming language syntax by using context-free grammars, which are considered the most widely used specification tool for this purpose. Then, it describes how to write syntax analyzers based on pushdown automata.
In theory, the book makes use of language-defining models to explore the very heart of the foundations of computation. That is, the text introduces the mathematical notion of a Turing machine, which has become a universally accepted formalization of the intuitive notion of a proce-dure. Based on this strictly mathematical notion, it studies the general limits of computation. More specifically, it performs this study in terms of two important topics concerning computation—computability and decidability. Regarding computability, it considers Turing machines as computers of functions over nonnegativeinteger sand demonstrates the existence of functions whose computation can not be specified by any procedure. As far as decidability is concerned, it formalizes problem-deciding algorithms by Turing machines that halt on every input. The book formulates several important problems concerning the language models discussed earlier in this book and constructs algorithms that decide them. On the other hand, it describes several problems that are not decidable by any algorithm. Apart from giving several specific undecidable problems, this book builds up a general theory of undecidability. Finally, the text approaches decidability in a much finer and realistic way. Indeed, it reconsiders problem-deciding algorithms in terms of their computational complexity measured according to time and space requirements. Perhaps most importantly, it shows that although some problems are decidable in principle, they are intractable for absurdly high computational requirements of the algorithms that decide them.
Use
As already stated, this book is intended as a textbook for a one-term introductory course informal language theory and its applications in computer science.
Second, the book can also be used as an accompanying textbook for a compiler class at an undergraduate level because the text allows the flexibility needed to select only the topics relevant to compilers.
Finally, this book is useful to all researchers, including people out of computer science, who somehow deal with formal languages and their models in their scientific fields.
Approach
Primarily, this book represents a theoretically oriented treatment of formal languages and their models. Indeed, it introduces all formalisms concerning them with enough rigor to make all results quite clear and valid. Every complicated mathematical passage is preceded by its intuitive explanation so that even the most complex parts of the book are easy to grasp. Every new concept or algorithm is preceded by an explanation of its purpose and followed by some examples with comments to reinforce its understanding. All applications are given in a quite realistic way to clearly demonstrate a strong relation between the theoretical concepts and their uses.
Secondarily, as already pointed out, the text also presents several significant applications of formal languages and their models in practice. All applications are given in a quite realistic way to clearly show a close relation between the theoretical concepts and their uses.
Prerequisites
On the part of the student, no previous knowledge concerning formal languages is assumed. Although this book is self-contained, in the sense that no other sources are needed for understand-ing the material, a familiarity with the rudiments of discrete mathematics is helpful for a quick comprehension of formal language theory. A familiarity with a high-level programming language helps to grasp the material concerning applications in this book.
Organization
Synopsis
The entire text contains 12 chapters, which are divided into 5 sections.
Section I, which consists of Chapters land 2, gives an introduction to the subject. Chapter 1 recalls the basic mathematical notions used in the book. Chapter 2 gives the basics of formal languages and rewriting systems that define them.
Section II, which consists of Chapters 3 through 5, studies regular languages and their models. Chapter 3 gives the basic dei nitions of these languages and their models, such as regular expressions and finite automata. Chapter 4is application oriented; specifically, it builds lexical analyzers by using models for regular languages. Chapter 5 studies properties concerning regular languages.
Section III, which consists of Chapters 6 through 8, discusses context-free languages and their models. To a large extent, its structure parallels Section II. Indeed, Chapter 6deines context-free languages and their models, including context-free grammars and pushdown automata. Chapter 7 explains how to construct syntax analyzers based on these grammars and automata. Chapter 8 establishes certain properties concerning context-free languages.
Section IV, which consists of Chapters 9 through 11, concerns Turing machines as a formalization of algorithms. Chapter 9 defines them. Based on Turing machines, Chapter 10 gives the basic ideas, concepts, and results underlying the theory of computation and its crucially impor-tant parts, including computability, decidability, and computational complexity. Simultaneously, this chapter establishes important properties concerning languages defined by Turing machines. Chapter 11 presents the essentials concerning general grammars, which represent grammatical counterparts to Turing machines.
Section V consists of Chapter 12. This chapter summarizes the entire textbook, points out selected modern trends, makes many historical and bibliographical remarks, and recommends further reading to the serious student.
Finally, the book contains two appendices. Appendix I gives the index to mathematical sym-bols used in the text. Appendix II contains the alphabetic index that lists all important language models introduced in the book.
Numbering
Regarding the technical organization of the text, algorithms, conventions, corollaries, definitions, lemmas, and theorems are sequentially numbered within chapters. Examples and figures are organized similarly. The end of conventions, corollaries, definitions, lemmas, and theorems is denoted by.
Exercises
At the end of each chapter, a set of exercises is given to reinforce and augment the material covered. Selected exercises, denoted by S, have their solutions or parts of them at the end of the chapter.
Algorithms
This textbook contains many algorithms. Strictly speaking, every algorithm requires a verification that it terminates and works correctly. However, the termination of the algorithms given in this book is always so obvious that its verification is omitted throughout. The correctness of complicated algorithms is verified in detail. On the other hand, we most often give only the gist of the straight forward algorithms and leave their rigorous verification as an exercise. The text describes the algorithms in Pascal-like notation, which is so simple and intuitive that even the student unfamiliar with the Pascal programming language can immediately pick it up. In this description, a Pascal repeat loop is sometimes ended with until no change, meaning that the loop is repeated until no change can result from its further repetition. As the clear comprehensibility is a paramount importance in the book, the description of algorithms is often enriched by an explanation in words.
Support on the World Wide Web
Further backup materials, including lecture notes,areavailableathttp://www.ft.vutbr.cz/~meduna/books/fc.

Preface xiii

Acknowledgments xvii

Author xix

SECTION I INTRODUCTION

1 Mathematical Background 3

      1.1 Logic 3

      1.2 Sets and Sequences 4

      1.3 Relations 6

      1.4 Graphs 7

2 Formal Languages and Rewriting Systems 13

      2.1 Formal Languages 13

      2.2 Rewriting Systems 15

      2.2.1 Rewriting Systems in General 16

      2.2.2 Rewriting Systems as Language Models 17

      2.2.3 Rewriting Systems as Computational Models 21

      2.3 Synopsis of the Book 25

SECTION II REGULAR LANGUAGES AND THEIR MODELS

3 Models for Regular Languages 31

      3.1 Finite Automata 31

      3.1.1 Representations of Finite Automata 32

      3.2 Restricted Finite Automata 34

      3.2.1 Removal of e-Rules 34

      3.2.2 Determinism 38

      3.2.2.1 Complete Specification 42

      3.2.3 Minimization 43

      3.3 Regular Expressions and Their Equivalence with Finite Automata 45

      3.3.1 Regular Expressions 45

      3.3.2 Equivalence with Finite Automata 47

      3.3.2.1 From Finite Automata to Regular Expressions 47

      3.3.2.2 From Regular Expressions to Finite Automata 49

4 Applications of Regular Expressions and Finite Automata: Lexical Analysis 61

      4.1 Implementation of Finite Automata 62

      4.1.1 Table-Based Implementation 62

      4.1.2 Case-Statement Implementation 64

      4.2 Introduction to Lexical Analysis 66

      4.2.1 Lexical Units and Regular Expressions 66

      4.2.2 Scanners and Finite Automata 66

      4.3 Implementation of a Scanner 67

5 Properties of Regular Languages 73

      5.1 Pumping Lemma for Regular Languages 73

      5.1.1 Applications of the Pumping Lemma for Regular Languages 75

      5.2 Closure Properties 77

      5.2.1 Applications of Closure Properties 80

SECTION III CONTEXT-FREE LANGUAGES AND THEIR MODELS

6 Models for Context-Free Languages 85

      6.1 Context-Free Grammars 85

      6.2 Restricted Context-Free Grammars 89

      6.2.1 Canonical Derivations and Derivation Trees 90

      6.2.1.1 Leftmost Derivations 90

      6.2.1.2 Rightmost Derivations 92

      6.2.1.3 Derivation Trees 92

      6.2.1.4 Ambiguity 94

      6.2.2 Removal of Useless Symbols 96

      6.2.3 Removal of Erasing Rules 99

      6.2.4 Removal of Single Rules 103

      6.2.5 Chomsky Normal Form 104

      6.2.6 Elimination of Left Recursion 106

      6.2.7 Greibach Normal Form 110

      6.3 Pushdown Automata 113

      6.3.1 Pushdown Automata and Their Languages 113

      6.3.2 Equivalence with Context-Free Grammars 114

      6.3.2.1 From Context-Free Grammars to Pushdown Automata 114

      6.3.2.2 From Pushdown Automata to Context-Free Grammars 115

      6.3.3 Equivalent Types of Acceptance 119

      6.3.4 Deterministic Pushdown Automata 121

7 Applications of Models for Context-Free Languages: Syntax Analysis 131

      7.1 Introduction to Syntax Analysis 132

      7.1.1 Syntax Specified by Context-Free Grammars 133

      7.1.2 Top-Down Parsing 134

      7.1.3 Bottom-Up Parsing 136

      7.2 Top-Down Parsing 141

      7.2.1 Predictive Sets and LL Grammars 142

      7.2.1.1 LL Grammars 145

      7.2.2 Predictive Parsing 146

      7.2.2.1 Predictive Recursive-Descent Parsing 146

      7.2.2.2 Predictive Table-Driven Parsing 149

      7.2.2.3 Handling Errors 153

      7.2.2.4 Exclusion of Left Recursion 154

      7.3 Bottom-Up Parsing 155

      7.3.1 Operator-Precedence Parsing 155

      7.3.1.1 Operator-Precedence Parser 156

      7.3.1.2 Construction of Operator-Precedence Parsing Table 158

      7.3.1.3 Handling Errors 159

      7.3.1.4 Operator-Precedence Parsers for Other Expressions 162

      7.3.2 LR Parsing 163

      7.3.2.1 LR Parsing Algorithm 164

      7.3.2.2 Construction of LR Table 167

      7.3.2.3 Handling Errors in LR Parsing 173

8 Properties of Context-Free Languages 187

      8.1 Pumping Lemma for Context-Free Languages 187

      8.1.1 Applications of the Pumping Lemma 189

      8.2 Closure Properties 189

      8.2.1 Union, Concatenation, and Closure 190

      8.2.2 Intersection and Complement 190

      8.2.3 Homomorphism 192

      8.2.4 Applications of the Closure Properties 192

SECTION IV TURING MACHINES AND COMPUTATION

9 Turing Machines and Their Variants 199

      9.1 Turing Machines and Their Languages 199

      9.2 Restricted Turing Machines 202

      9.2.1 Computational Restrictions 203

      9.2.2 Size Restrictions 205

      9.3 Universal Turing Machines 206

      9.3.1 Turing Machine Codes 206

      9.3.2 Construction of Universal Turing Machines 208

10 Applications of Turing Machines: Theory of Computation 213

      10.1 Computability 214

      10.1.1 Integer Functions Computed by Turing Machines 214

      10.1.2 Recursion Theorem 217

      10.1.3 Kleene'ss-m-n Theorem 219

      10.2 Decidability 220

      10.2.1 Turing Deciders 220

      10.2.2 Decidable Problems 223

      10.2.2.1 Decidable Problems for Finite Automata 223

      10.2.2.2 Decidable Problems for Context-Free Grammars 225

      10.2.3 Undecidable Problems 227

      10.2.3.1 Diagonalization 228

      10.2.3.2 Reduction 230

      10.2.3.3 Undecidable Problems Not Concerning Turing Machines 233

      10.2.4 General Approach to Undecidability 234

      10.2.4.1 Rice's Theorem.237

      10.2.5 Computational Complexity 238

      10.2.5.1 Time Complexity 238

      10.2.5.2 Space Complexity 240

11 Turing Machines and General Grammars 245

      11.1 General Grammars and Their Equivalence with Turing Machines 245

      11.1.1 General Grammars 245

      11.1.2 Normal Forms 246

      11.1.3 Equivalence of General Grammars and Turing Machines 248

      11.1.3.1 From General Grammars to Turing Machines 248

      11.1.3.2 From Turing Machines to General Grammars 249

      11.2 Context-Sensitive Grammars and Linear-Bounded Automata 250

      11.2.1 Context-Sensitive Grammars and Their Normal Forms 250

      11.2.1.1 Normal Forms 251

      11.2.2 Linear-Bounded Automata and Their Equivalence with Context-Sensitive Grammars 251

      11.2.2.1 From Context-Sensitive Grammars to Linear-Bounded Automata 251

      11.2.2.2 From Linear-Bounded Automata to Context-Sensitive Grammars 252

      11.2.3 Context-Sensitive Languages and Decidable Languages 253

      11.3 Relations between Language Families 254

SECTION V CONCLUSION

12 Concluding and Bibliographical Remarks 261

      12.1 Summary 261

      12.2 Modern Trends 263

      12.2.1 Conditional Grammars 263

      12.2.2 Regulated Grammars 263

      12.2.3 Scattered Context Grammars 264

      12.2.4 Grammar Systems 264

      12.3 Bibliographical and Historical Remarks 264

Appendix I: Index to Special Symbols 269

Appendix II: Index to Language Models 271

References 273

Bibliography 279

Index 289

Alexander Meduna, PhD, is a full professor of computer science at the Brno University of Technology in the Czech Republic, where he earned his doctorate in 1988. From 1988 until 1997, he taught computer science at the University of Missouri-Columbia in the United States. Even more intensively, since 2000, he has taught computer science and mathematics at the Brno University of Technology. In addition to these two universities, he has taught computer science at several other American, European, and Japanese universities for shorter periods of time. His classes have been primarily focused on formal language theory and its applications in theoretical and practical computer science. His teaching has also covered various topics including automata, discrete mathematics, operating systems, and principles of programming languages. Among many other awards for his scholarship and writing, he received the Distinguished University Professor Award from Siemens in 2012. He very much enjoys teaching classes related to the subject of this book. PA\Dr. Meduna has written several books. Specifically, he is the author of two textbooks—Automata and Languages (Springer, 2000) and Elements of Compiler Design (Taylor & Francis, 2008; trans-lated into Chinese in 2009) . Furthermore, he is the coauthor of three monographs—Grammars with Context Conditions and Their Applications (along with Martin Svec, Wiley, 2005) , Scattered Context Grammars and Their Applications (with Jiri Techet, WIT Press, 2010) , and Regulated Grammars and Automata (with Petr Zemek, Springer, 2014) . He has published over 90 studies in prominent inter-national journals, such as Acta Informatica (Springer) , International Journal of Computer Mathematics (Taylor & Francis) , and Theoretical Computer Science (Elsevier) . All his scientific work discusses the theory of formal languages and computation, the subject of this book, or closely related topics, such as compiler writing. PA\Alexander Meduna's website is http://www.fit.vutbr.cz/~meduna. His scientific work is described in detail at http://www.fit.vutbr.cz/~meduna/work.

中科院文献情报中心