形式语言与自动机导论：英文版

Chapter1 Introduction to the Theory of Computation
1.1 Mathematical Preliminaries and Notation
Sets
Functions and Relations
Graphs and Trees
Proof Techniques
1.2 Three Basic Concepts
Languages
Grammars
Automata
1.3 Some Applications
Chapter2 Finite Automata
2.1 Deterministic Finite Accepters
Deterministic Accepters and Transition Graphs
Languages and Dfas
Regular Languages
2.2 Nondeterministic Finite Accepters
Definition of a Nondeterministic Accepter
Why Nondeterminism?
2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters
2.4 Reduction of the Number of States in Finite Automata
Chapter3 Regular Languages and Regular Grammars
3.1 Regular Expressions
Formal Definition of a Regular Expression
Languages Associated with Regular Expressions
3.2 Connection Between Regular Expressions and Regular Languages
Regular Expressions Denote RegularLanguages
Regular Expressions for Regular Languages
Regular Expressions for Describing Simple Patterns
3.3 Regular Grammars
Right-and Left-Linear Grammars
Right-Linear Grammars Generate Regular Languages
Right-Linear Grammars for Regular Languages
Equivalence Between Regular Languages and Regular Grammars
Chapter4 Properties of Regular Languages
4.1 Closure Properties of Regular Languages
Closure under Simple Set Operations
Closure under Other Operations
4.2 Elementary Questions about Regular Languages
4.3 Identifying Nonregular Languages
Using the pigeonhole Principle
A Pumping Lemma
Chapter5 Context-Free Languages
5.1 Context-Free Grammars
Examples of Context-Free Languages
Leftmost and Rightmost Derivations
Derivation Trees
Relation Between Sentential Forms and Derivation Trees
5.2 Parsing and Ambiguity
Parsing ang Membership
Ambiguity in Grammars and Languages
5.3 Context-Free Grammars and Programming Languages
Chapter6 Simplification lf Context-Free Grammars
6.1 Methods for Transforming Grammars
A Useful Substitution Rule
Removing Useless Productions
Removing
Removing Unit-Productions
6.2 Two Important Normal Forms
Chomsky Normal Form
Greibach Normal Form
6.3 A Membership Algorithm for Context-free Grammars
Chapter7 Pushdown Automata
7.1 Nondeterministic Pushown Automata
Definition of a Pushdown Automata
A Language Accepted by a Pushdown Automaton
7.2 Pushdown Automata and Context-Free Languages
Pushdown Automata for Context-Free Languages
Context-Free Grammars for Pushdown Automata
7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages
7.4 Grammars for Deterministic Context-Free Languages
Chapter8 Properties Context-Free Languages
8.1 Two Pumping Lemmas
A Pumping Lemma for Context-Free Languages
A Pumping Lemma for Linear Languages
8.2 Closure Properties and Decision Algorithms for Context-Free Languages
Closure of Context-Free Languages
Some Decidable Properties of Context-Free Languages
Chapter9 Turing Machines
9.1 The Standard Turing Machine
Definition of a Turing Machine
Turing Machines as Language Accepters
Turing Machines asTransducers
9.2 Combining Turing Machines for Complicated Tasds
9.3 Turing’s Thesis
Chapter10 Other ModeIs of Turing Machines
10.1 Minor Variations on the Turing Machine Theme
Equivalence of Classes of Automata
Turing Machines with a Stay-Option
Turing Machines with Semi-Infinite Tape
The Off-Line Tuing Machines
10.2 Turing Machines with More Complex Storage
Multitape Turing Machines
Multidimensional Turing Machines
10.3 Nondeterministic Turing Machines
10.4 A Universal Turing Machine
10.5 Linear Bounded Automata
Chapter11 A Hierardhy of Formal Languages and Automata
11.1 Recursive and Recursively Enumerable Languages
Languages That Are Not Recursively Enumerable
A Language That Is Not Recursively Enumerable
A Language That Is Recursively Enumerable But Not Recursive
11.2 Unrestricted Grammars
11.3 Context-Sensitive Grammars and Languages
Context-Sensitive Languages and Linear Bounded Automata
Relation Between Recursive and Context-Sensitive Languages
11.4 The Chomsky Hierarchy
Chapter12 Limits of Algorithmic Computation
12.1 SomeProblems That Cannot Be Solved By Turing Machines
The Turing Machine Halting Problem
Reducing One Undecidable Problem to Another
12.2 Undecidable Prolems for Recursively Enumerable Languages
12.3 The Post Correspondence Problem
12.4 Undecidable Problems for Context-free Languages
Chapter13 Other Models Computation
13.1 Recursive Functions
Primitive Recursive Functions
Ackermann’s Function
13.2 Post Systems
13.3 Rewriting Systems
Markov Alglrithms
L-Systems
Chapter14  An Introduction to Computational complexity
14.1 Effciency of Computation
14.2 Turing Machines and Complexity Classes
14.3 Language Families and Complexity Classes
14.4 The Complexity Classes P and NP
Answers to Selected Exercises
References
Index