| |
| |
| |
| Introduction | |
| |
| |
| |
| Why Study Automata Theory? | |
| |
| |
| |
| Review of Mathematical Concepts | |
| |
| |
| |
| Logic | |
| |
| |
| |
| Sets | |
| |
| |
| |
| Relations | |
| |
| |
| |
| Functions | |
| |
| |
| |
| Closures | |
| |
| |
| |
| Proof Techniques | |
| |
| |
| |
| Reasoning about Programs | |
| |
| |
| |
| References | |
| |
| |
| |
| Languages and Strings | |
| |
| |
| |
| Strings | |
| |
| |
| |
| Languages | |
| |
| |
| |
| The Big Picture: A Language Hierarchy | |
| |
| |
| |
| Defining the Task: Language Recognition | |
| |
| |
| |
| The Power of Encoding | |
| |
| |
| |
| A Hierarchy of Language Classes5 Computation | |
| |
| |
| |
| Decision Procedures | |
| |
| |
| |
| Determinism and Nondeterminism | |
| |
| |
| |
| Functions on Languages and Programs | |
| |
| |
| |
| Finite State Machines and Regular Languages | |
| |
| |
| |
| Finite State Machines | |
| |
| |
| |
| Deterministic Finite State Machines | |
| |
| |
| |
| The Regular Languages | |
| |
| |
| |
| Programming Deterministic Finite State Machines | |
| |
| |
| |
| Nondeterministic FSMs | |
| |
| |
| |
| Interpreters for FSMs | |
| |
| |
| |
| Minimizing FSMs | |
| |
| |
| |
| Finite State Transducers | |
| |
| |
| |
| Bidirectional Transducers | |
| |
| |
| |
| Stochastic Finite Automata | |
| |
| |
| |
| Finite Automata, Infinite Strings: Buchi Automata | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Regular Expressions | |
| |
| |
| |
| What is a Regular Expression? | |
| |
| |
| |
| Kleene's Theorem | |
| |
| |
| |
| Applications of Regular Expressions | |
| |
| |
| |
| Manipulating and Simplifying Regular Expressions | |
| |
| |
| |
| Regular Grammars | |
| |
| |
| |
| Definition of a Regular Grammar | |
| |
| |
| |
| Regular Grammars and Regular Languages | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Regular and Nonregular Languages | |
| |
| |
| |
| How Many Regular Languages Are There? | |
| |
| |
| |
| Showing That a Language Is Regular.124 | |
| |
| |
| |
| Some Important Closure Properties of Regular Languages | |
| |
| |
| |
| Showing That a Language is Not Regular | |
| |
| |
| |
| Exploiting Problem-Specific Knowledge | |
| |
| |
| |
| Functions on Regular Languages | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Algorithms and Decision Procedures for Regular Languages | |
| |
| |
| |
| Fundamental Decision Procedures | |
| |
| |
| |
| Summary of Algorithms and Decision Procedures for Regular Languages | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Summary and References | |
| |
| |
| |
| Context-Free Languages and Pushdown Automata 144 | |
| |
| |
| |
| Context-Free Grammars | |
| |
| |
| |
| Introduction to Grammars | |
| |
| |
| |
| Context-Free Grammars and Languages | |
| |
| |
| |
| Designing Context-Free Grammars | |
| |
| |
| |
| Simplifying Context-Free Grammars | |
| |
| |
| |
| Proving That a Grammar is Correct | |
| |
| |
| |
| Derivations and Parse Trees | |
| |
| |
| |
| Ambiguity | |
| |
| |
| |
| Normal Forms | |
| |
| |
| |
| Stochastic Context-Free Grammars | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Pushdown Automata | |
| |
| |
| |
| Definition of a (Nondeterministic) PDA | |
| |
| |
| |
| Deterministic and Nondeterministic PDAs | |
| |
| |
| |
| Equivalence of Context-Free Grammars and PDAs | |
| |
| |
| |
| Nondeterminism and Halting | |
| |
| |
| |
| Alternative Definitions of a PDA | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Context-Free and Noncontext-Free Languages | |
| |
| |
| |
| Where Do the Context-Free Languages Fit in the Big Picture? | |
| |
| |
| |
| Showing That a Language is Context-Free | |
| |
| |
| |
| The Pumping Theorem for Context-Free Languages | |
| |
| |
| |
| Some Important Closure Properties of Context-Free Languages | |
| |
| |
| |
| Deterministic Context-Free Languages | |
| |
| |
| |
| Other Techniques for Proving That a Language is Not Context-Free | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Algorithms and Decision Procedures for Context-Free Languages | |
| |
| |
| |
| Fundamental Decision Procedures | |
| |
| |
| |
| Summary of Algorithms and Decision Procedures for Context-Free Languages | |
| |
| |
| |
| Context-Free Parsing | |
| |
| |
| |
| Lexical Analysis | |
| |
| |
| |
| Top-Down Parsing | |
| |
| |
| |
| Bottom-Up Parsing | |
| |
| |
| |
| Parsing Natural Languages | |
| |
| |
| |
| Stochastic Parsing | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Summary and References | |
| |
| |
| |
| Turing Machines and Undecidability | |
| |
| |
| |
| Turing Machines | |
| |
| |
| |
| Definition, Notation and Examples | |
| |
| |
| |
| Computing With Turing Machines | |
| |
| |
| |
| Turing Machines: Extensions and Alternativ | |