经典原版书库·自动机理论：语言和计算机导论（英文版）（第3版）
1 Automata: The Methods and the Madness
1.1 Why Study Automata Theory?
1.1.1 Introduction to Finite Automata
1.1.2 Structural Representations
1.1.3 Automata and Complexity
1.2 Introduction to Formal Proof
1.2.1 Deductive Proofs
1.2.2 Reduction to Definitions
1.2.3 Other Theorem Forms
1.2.4 Theorems That Appear Not to …
查看完整
1.1 Why Study Automata Theory?
1.1.1 Introduction to Finite Automata
1.1.2 Structural Representations
1.1.3 Automata and Complexity
1.2 Introduction to Formal Proof
1.2.1 Deductive Proofs
1.2.2 Reduction to Definitions
1.2.3 Other Theorem Forms
1.2.4 Theorems That Appear Not to …
查看完整
John E.Hopcroft，于斯坦福大学获得博士学位，现为康奈尔大学计算机科学系教授。1994年到2001年，任康奈尔大学工程学院院长。他是1986年图灵奖获得者。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。
《自动机理论：语言和计算机导论》（英文版）（第3版）是关于形式语言、自动机理论和计算复杂性方面的经典教材，是三位理论计算大师的巅峰之作，现已更新到第3版。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的，陸质、图灵机、不可判定性以及难解问题等内容。
1 Automata: The Methods and the Madness
1.1 Why Study Automata Theory?
1.1.1 Introduction to Finite Automata
1.1.2 Structural Representations
1.1.3 Automata and Complexity
1.2 Introduction to Formal Proof
1.2.1 Deductive Proofs
1.2.2 Reduction to Definitions
1.2.3 Other Theorem Forms
1.2.4 Theorems That Appear Not to Be If-Then Statements
1.3 Additional Forms of Proof
1.3.1 Proving Equivalences About Sets
1.3.2 The Contrapositive
1.3.3 Proof by Contradiction
1.3.4 Counterexamples
1.4 Inductive Proofs
1.4.1 Inductions on Integers
1.4.2 More General Forms of Integer Inductions
1.4.3 Structural Inductions
1.4.4 Mutual Inductions
1.5 The Central Concepts of Automata Theory
1.5.1 Alphabets
1.5.2 , Strings
1.5.3 Languages
1.5.4 Problems
1.6 Summary of Chapter 1
1.7 Gradiance Problems for Chapter 1
1.8 References for Chapter 1
2 Finite Automata
2.1 An Informal Picture of Finite Automata
2.1.1 The Ground Rules
2.1.2 The Protocol
2.1.3 Enabling the Automata to Ignore Actions
2.1.4 The Entire System as an Automaton
2.1.5 Using the Product Automaton to Validate the Protocol
2.2 Deterministic Finite Automata
2.2.1 Definition of a Deterministic Finite Automaton
2.2.2 How a DFA Processes Strings
2.2.3 Simpler Notations for DFAs
2.2.4 Extending the Transition Function to Strings
2.2.5 The Language of a DFA
2.2.6 Exercises for Section 2.2
2.3 Nondeterministic Finite Automata
2.3.1 An Informal View of Nondeterministic Finite Automata
2.3.2 Definition of Nondeterministic Finite Automata
2.3.3 The Extended Transition Function
2.3.4 The Language of an NFA
2.3.5 Equivalence of Deterministic and Nondeterministic Finite Automata
2.3.6 A Bad Case for the Subset Construction
2.3.7 Exercises for Section 2.3
2.4 An Application: Text Search
2.4.1 Finding Strings in Text
2.4.2 Nondeterministic Finite Automata for Text Search
2.4.3 A DFA to Recognize a Set of Keywords
2.4.4 Exercises for Section 2.4
2.5 Finite Automata With Epsilon-Transitions
2.5.1 Uses of e-Transitions
2.5.2 The Formal Notation for an c-NFA
2.5.3 Epsilon-Closures
2.5.4 Extended Transitions and Languages for c-NFAs
2.5.5 Eliminating e-Transitions
2.5.6 Exercises for Section 2.5
2.6 Summary of Chapter 2
2.7 Gradiance Problems for Chapter 2
2.8 References for Chapter 2
3 Regular Expressions and Languages
3.1 Regular Expressions
3.1.1 The Operators of Regular Expressions
3.1.2 Building Regular Expressions
3.1.3 Precedence of Regular-Expression Operators
3.1.4 Exercises for Section 3.1
3.2 Finite Automata and Regular Expressions
3.2.1 From DFAs to Regular Expressions
3.2.2 Converting DFAs to Regular Expressions by Eliminating States
……
4 Properties kf Regular Languages
5 Context-Free Grammars and Languages
6 Pushdown Automata
7 Properties of Context-Free Languages
8 Introduction to Turing Machines
9 Undecidability
10 Intractable Problems
11 Additional Classes of Problems
Index
^ 收 起
1.1 Why Study Automata Theory?
1.1.1 Introduction to Finite Automata
1.1.2 Structural Representations
1.1.3 Automata and Complexity
1.2 Introduction to Formal Proof
1.2.1 Deductive Proofs
1.2.2 Reduction to Definitions
1.2.3 Other Theorem Forms
1.2.4 Theorems That Appear Not to Be If-Then Statements
1.3 Additional Forms of Proof
1.3.1 Proving Equivalences About Sets
1.3.2 The Contrapositive
1.3.3 Proof by Contradiction
1.3.4 Counterexamples
1.4 Inductive Proofs
1.4.1 Inductions on Integers
1.4.2 More General Forms of Integer Inductions
1.4.3 Structural Inductions
1.4.4 Mutual Inductions
1.5 The Central Concepts of Automata Theory
1.5.1 Alphabets
1.5.2 , Strings
1.5.3 Languages
1.5.4 Problems
1.6 Summary of Chapter 1
1.7 Gradiance Problems for Chapter 1
1.8 References for Chapter 1
2 Finite Automata
2.1 An Informal Picture of Finite Automata
2.1.1 The Ground Rules
2.1.2 The Protocol
2.1.3 Enabling the Automata to Ignore Actions
2.1.4 The Entire System as an Automaton
2.1.5 Using the Product Automaton to Validate the Protocol
2.2 Deterministic Finite Automata
2.2.1 Definition of a Deterministic Finite Automaton
2.2.2 How a DFA Processes Strings
2.2.3 Simpler Notations for DFAs
2.2.4 Extending the Transition Function to Strings
2.2.5 The Language of a DFA
2.2.6 Exercises for Section 2.2
2.3 Nondeterministic Finite Automata
2.3.1 An Informal View of Nondeterministic Finite Automata
2.3.2 Definition of Nondeterministic Finite Automata
2.3.3 The Extended Transition Function
2.3.4 The Language of an NFA
2.3.5 Equivalence of Deterministic and Nondeterministic Finite Automata
2.3.6 A Bad Case for the Subset Construction
2.3.7 Exercises for Section 2.3
2.4 An Application: Text Search
2.4.1 Finding Strings in Text
2.4.2 Nondeterministic Finite Automata for Text Search
2.4.3 A DFA to Recognize a Set of Keywords
2.4.4 Exercises for Section 2.4
2.5 Finite Automata With Epsilon-Transitions
2.5.1 Uses of e-Transitions
2.5.2 The Formal Notation for an c-NFA
2.5.3 Epsilon-Closures
2.5.4 Extended Transitions and Languages for c-NFAs
2.5.5 Eliminating e-Transitions
2.5.6 Exercises for Section 2.5
2.6 Summary of Chapter 2
2.7 Gradiance Problems for Chapter 2
2.8 References for Chapter 2
3 Regular Expressions and Languages
3.1 Regular Expressions
3.1.1 The Operators of Regular Expressions
3.1.2 Building Regular Expressions
3.1.3 Precedence of Regular-Expression Operators
3.1.4 Exercises for Section 3.1
3.2 Finite Automata and Regular Expressions
3.2.1 From DFAs to Regular Expressions
3.2.2 Converting DFAs to Regular Expressions by Eliminating States
……
4 Properties kf Regular Languages
5 Context-Free Grammars and Languages
6 Pushdown Automata
7 Properties of Context-Free Languages
8 Introduction to Turing Machines
9 Undecidability
10 Intractable Problems
11 Additional Classes of Problems
Index
^ 收 起
John E.Hopcroft，于斯坦福大学获得博士学位，现为康奈尔大学计算机科学系教授。1994年到2001年，任康奈尔大学工程学院院长。他是1986年图灵奖获得者。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。
《自动机理论：语言和计算机导论》（英文版）（第3版）是关于形式语言、自动机理论和计算复杂性方面的经典教材，是三位理论计算大师的巅峰之作，现已更新到第3版。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的，陸质、图灵机、不可判定性以及难解问题等内容。
比价列表
