語言與機器：計算機科學理論導論（第3版）（簡體書）

本書介紹了計算機科學的基礎知識，以及各種算法計算的能力和局限性。本書通過大量示例，以一種直觀、易懂的方式闡釋了計算機科學理論的概念及相關數學知識。第3版還擴展介紹了自動機理論、計算理論和計算復雜性等內容。 本書可作為計算機及相關專業的計算機科學理論課程的教材。

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