Transcription
Automata, Computability and Complexity:Theory and ApplicationsElaine Rich
Originally published in by Pearson Education, Inc. Elaine RichWith minor revisions, July.
Table of ContentsPREFACE .VIIIACKNOWLEDGEMENTS.XICREDITS.XIIPART I: INTRODUCTION. 11Why Study the Theory of Computation? .21.1 The Shelf Life of Programming Tools .21.2 Applications of the Theory Are Everywhere .42Languages and Strings .62.1 Strings . 62.2 Languages . 72.3 Exercises . 143The Big Picture: A Language Hierarchy . 163.1 Defining the Task: Language Recognition . 163.2 The Power of Encoding . 163.3 A Machine-Based Hierarchy of Language Classes . 213.4 A Tractability Hierarchy of Language Classes . 253.5 Exercises . 254Computation . 274.1 Decision Procedures . 274.2 Determinism and Nondeterminism . 304.3 Functions on Languages and Programs . 354.4 Exercises . 37PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES . 395Finite State Machines . 405.1 Deterministic Finite State Machines . 405.2 The Regular Languages . 445.3 Designing Deterministic Finite State Machines . 465.4 Nondeterministic FSMs . 485.5 From FSMs to Operational Systems . 585.6 Simulators for FSMs . 585.7 Minimizing FSMs . 605.8 A Canonical Form for Regular Languages . 695.9 Finite State Transducers . 705.10Bidirectional Transducers . 715.11Stochastic Finite Automata: Markov Models and HMMs . 735.12Finite Automata, Infinite Strings: Büchi Automata . 835.13Exercises . 876Regular Expressions . 926.1 What is a Regular Expression? . 92i
6.26.36.46.5Kleene’s Theorem . 95Applications of Regular Expressions . 106Manipulating and Simplifying Regular Expressions . 108Exercises . 1097Regular Grammars . 1137.1 Definition of a Regular Grammar. 1137.2 Regular Grammars and Regular Languages . 1147.3 Exercises . 1178Regular and Nonregular Languages . 1188.1 How Many Regular Languages Are There? . 1188.2 Showing That a Language Is Regular . 1188.3 Some Important Closure Properties of Regular Languages. 1198.4 Showing That a Language is Not Regular . 1238.5 Exploiting Problem-Specific Knowledge . 1298.6 Functions on Regular Languages . 1308.7 Exercises . 1329Algorithms and Decision Procedures for Regular Languages . 1369.1 Fundamental Decision Procedures . 1369.2 Summary of Algorithms and Decision Procedures for Regular Languages . 1419.3 Exercises . 14210Summary and References . 143PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA . 14511Context-Free Grammars . 14611.1Introduction to Rewrite Systems and Grammars . 14611.2Context-Free Grammars and Languages . 14911.3Designing Context-Free Grammars . 15311.4Simplifying Context-Free Grammars . 15411.5Proving That a Grammar is Correct . 15511.6Derivations and Parse Trees . 15711.7Ambiguity . 15911.8Normal Forms . 16811.9Island Grammars . 17511.10 Stochastic Context-Free Grammars . 17711.11 Exercises . 17812Pushdown Automata . 18212.1Definition of a (Nondeterministic) PDA . 18212.2Deterministic and Nondeterministic PDAs. 18512.3Equivalence of Context-Free Grammars and PDAs . 19012.4Nondeterminism and Halting . 19912.5Alternative Equivalent Definitions of a PDA . 2.6Alternatives that are Not Equivalent to the PDA . 2.7Exercises . 3Context-Free and Noncontext-Free Languages . 3.1Where Do the Context-Free Languages Fit in the Big Picture? . 3.2Showing That a Language is Context-Free. 3.3The Pumping Theorem for Context-Free Languages . 3.4Some Important Closure Properties of Context-Free Languages . 209ii
13.513.613.713.813.9Deterministic Context-Free Languages . 214Ogden’s Lemma . 220Parikh’s Theorem . 223Functions on Context-Free Languages . 225Exercises . 22614Algorithms and Decision Procedures for Context-Free Languages. 22914.1The Decidable Questions .