ABSTRACT
This concluding chapter consists of three sections� Section 12�1 summarizes this book� Section 12�2 outlines selected modern trends, which were omitted in this book� Section 12�3 places all its material into a historical and bibliographical context; in addition, it recommends further reading to the serious student�
12.1 Summary This book gives an introduction to the theory of formal languages and its applications in computer science� It is meant as the basis of a one-term undergraduate-level course on this subject� The text maintains a balance between a theoretical and practical approach to this subject� From a theoretical viewpoint, it covers all rudimental topics concerning formal languages and their models, especially grammars and automata� The book shows basic properties of languages defined by these models� Concerning applications, it explains how these models underlie computer science engineering techniques for language processing, such as lexical and syntax analysis� From a more theoretical viewpoint, this book applies these models to computation in general and, thereby, shows the basic ideas underlying the theory of computation, including computability, decidability, and computational complexity�
This book is divided into five sections� Section I, consisting of Chapters 1 and 2, gives an introduction to this book� Chapter 1 reviews
basic mathematical notions needed to follow the rest of this book� Chapter 2 first defines formal languages and rewriting systems, and based on these systems, it conceptualizes (i) language-defining models and (ii) models of computation�
Section II, consisting of Chapters 3 through 5, discusses regular languages and their models� Chapter 3 introduces finite automata (FAs) and regular expressions (REs) as fundamental language
262
models that characterize the family of regular languages, denoted by regΦ (see Theorem 3�38)� In fact, regarding FAs, this chapter defines a broad variety of these automata and shows their equivalence (see Corollary 3�22)� Chapter 4 describes applications of REs and FAs in lexical analysis� Chapter 5 establishes important properties of regular languages� It concentrates its attention on establishing properties that allow us to prove or, in contrast, disprove that a given language is regular�
Section III, consisting of Chapters 6 through 8, covers context-free languages and their models� Chapter 6 introduces context-free grammars (CFGs) and pushdown automata (PDAs) as language-generating models and language-accepting models, respectively, and it shows that both characterize the family of context-free languages, CFG Φ (see Theorem 6�57)� Chapter 6 also shows that deterministic versions of PDAs are less powerful than their nondeterministic counterparts (see Theorem 6�71)� Chapter 7 applies CFGs and PDAs to the syntax analysis of programming languages� Both top-down and bottom-up parsers are covered in this chapter in detail� In many respects, Chapter 8 parallels Chapter 5; however, Chapter 8 obviously studies language properties in terms of CFG Φ� That is, it shows several properties concerning CFG Φ and explains how to use them to answer whether or not certain languages are in CFG Φ�
Section IV, consisting of Chapters 9 through 11, defines important language-accepting rewriting systems referred to as Turing machines (TMs) and uses them primarily as models of computation� Chapter 9 defines them� Based on TMs, Chapter 10 outlines the theory of computation, including computability, decidability, and computational complexity� To link TMs to the theory of formal languages, Chapter 11 defines their grammatical counterparts (see Section 11�1)� It also considers TM Φ as the family of languages defined by TMs and establishes
finΦ ⊂ regΦ ⊂ CFGΦ ⊂ TMΦ ⊂ all Φ
where finΦ and all Φ denote the family of finite languages and the entire family of all languages, respectively (see Convention 2�1 and Theorem 11�24)�
Section V, consisting of this chapter, closes this book by summarizing its material, outlining selected modern topics and placing its subject into a historical and bibliographical context�
This book has paid special attention to closure properties� Most of them were proved in Sections 5�2, 8�2, and 10�2; some of them were established as exercises (see Exercise 12 in Chapter 11)� In Figure 12�1, which closes this section, we summarize the closure properties of regΦ, CFGΦ, and TMΦ under operations union (∪), concatenation (�), closure (*), intersection (∩), and complement (~)�
Figure 12.1 Summary of closure properties.
