Pretace IntroductiOn PART I Foundations Chapter 1 MathematicaI Preliminaries 1.1 SetTheory 1.2 Cartesian Product，Relations，and Functions 1.3 Equivalence Relations 1.4 Countable and Uncountable Sets 1.5 DiagonalizatiOn and Self-Reference 1.6 Recursive Definitions 1.7 Mathematical Induction 1.8 Directed Graphs Exercises Bibliographic Notes Chapter 2 Languages 2.1 Strings and Languages 2.2 Finite Specification of Languages 2.3 Regular Sets and Expressions 2.4 Regular Expressions and Text Searching Exercises Bibliographic Notes PART II Grammars，Automata，and Languages Chapter 3 Context-Free Grammars 3.1 Context-Free Grammars and Languages 3.2 Examples of Grammars and Languages 3.3 Regular Grammars 3.4 Verifying Grammars 3.5 Leftmost Derivations and Ambiguity 3.6 Context-Free Grammars and Programming Language Definition Exercises Bibliographic Notes Chapter 4 NormaI Forms for Context-Free Grammars 4.1 Grammar Transformations 4.2 Elimination ofλ-Rules 4.3 Elimination of Chin Rules 4.4 Useless Symbols 4.5 Chomsky Normal Form 4.6 The CYK Algorithm 4.7 Removal of Direct Left Recursion 4.8 Greibach Normal Form Exercises Bibliographic NOtes Chapter 5 Finite AutGImata 5.1 A Finite.State Machine 5.2 Deterministic Finite AutOmata 5.3 State Diagrams and Examples 5.4 Nondeterministic Finite Automata 5.5 λ-Transitions 5.6 Removing Nondeterminism 5.7 DFA Minimization
Exercises Bibliographic Notes …… PART III Computability PART IV Computational Complexity PART V Deterministic Parsing Appendix Bibliography Subject Index
