自动机理论与应用 影印版PDF|Epub|txt|kindle电子书版本下载

自动机理论与应用 影印版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

PART Ⅰ:INTRODUCTION1

1 Why Study the Theory of Computation?2

1.1 The Shelf Life of Programming Tools2

1.2 Applications of the Theory Are Everywhere5

2 Languages and Strings8

2.1 Strings8

2.2 Languages10

Exercises19

3 The Big Picture:A Language Hierarchy21

3.1 Defining the Task:Language Recognition21

3.2 The Power of Encoding22

3.3 A Machine-Based Hierarchy of Language Classes28

3.4 A Tractability Hierarchy of Language Classes34

Exercises34

4 Computation36

4.1 Decision Procedures36

4.2 Determinism and Nondeterminism41

4.3 Functions on Languages and Programs48

Exercises52

PART Ⅱ:FINITE STATE MACHINES AND REGULAR LANGUAGES53

5 Finite State Machines54

5.1 Deterministic Finite State Machines56

5.2 The Regular Languages60

5.3 Designing Deterministic Finite State Machines63

5.4 Nondeterministic FSMs66

5.5 From FSMs to Operational Systems79

5.6 Simulators for FSMs80

5.7 Minimizing FSMs82

5.8 A Canonical Form for Regular Languages94

5.9 Finite State Transducers96

5.10 Bidirectional Transducers98

5.11 Stochastic Finite Automata:Markov Models and HMMs101

5.12 Finite Automata,Infinite Strings:Büchi Automata115

Exercises121

6 Regular Expressions127

6.1 What is a Regular Expression?128

6.2 Kleene's Theorem133

6.3 Applications of Regular Expressions147

6.4 Manipulating and Simplifying Regular Expressions149

Exercises151

7 Regular Grammars155

7.1 Definition of a Regular Grammar155

7.2 Regular Grammars and Regular Languages157

Exercises161

8 Regular and Nonregular Languages162

8.1 How Many Regular Languages Are There?162

8.2 Showing That a Language Is Regular163

8.3 Some Important Closure Properties of Regular Languages165

8.4 Showing That a Language is Not Regular169

8.5 Exploiting Problem-Specific Knowledge178

8.6 Functions on Regular Languages179

Exercises182

9 Algorithms and Decision Procedures for Regular Languages187

9.1 Fundamental Decision Procedures187

9.2 Summary of Algorithms and Decision Procedures for Regular Languages194

Exercises196

10 Summary and References198

References199

PART Ⅲ:CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA201

11 Context-Free Grammars203

11.1 Introduction to Rewrite Systems and Grammars203

11.2 Context-Free Grammars and Languages207

11.3 Designing Context-Free Grammars212

11.4 Simplifying Context-Free Grammars212

11.5 Proving That a Grammar is Correct215

11.6 Derivations and Parse Trees218

11.7 Ambiguity220

11.8 Normal Forms232

11.9 Island Grammars241

11.10 Stochastic Context-Free Grammars243

Exercises245

12 Pushdown Automata249

12.1 Definition of a(Nondeterministic)PDA249

12.2 Deterministic and Nondeterministic PDAs254

12.3 Equivalence of Context-Free Grammars and PDAs260

12.4 Nondeterminism and Halting274

12.5 Alternative Equivalent Definitions of a PDA275

12.6 Alternatives that are Not Equivalent to the PDA277

Exercises277

13 Context-Free and Noncontext-Free Languages279

13.1 Where Do the Context-Free Languages Fit in the Big Picture?279

13.2 Showing That a Language is Context-Free280

13.3 The Pumping Theorem for Context-Free Languages281

13.4 Some Important Closure Properties of Context-Free Languages288

13.5 Deterministic Context-Free Languages295

13.6 Ogden's Lemma303

13.7 Parikh's Theorem306

13.8 Functions on Context-Free Languages308

Exercises310

14 Algorithms and Decision Procedures for Context-Free Languages314

14.1 The Decidable Questions314

14.2 The Undecidable Questions320

14.3 Summary of Algorithms and Decision Procedures for Context-Free Languages320

Exercises322

15 Context-Free Parsing323

15.1 Lexical Analysis325

15.2 Top-Down Parsing327

15.3 Bottom-Up Parsing340

15.4 Parsing Natural Languages350

Exercises358

16 Summary and References360

References360

PART Ⅳ:TURING MACHINES AND UNDECIDABILITY363

17 Turing Machines364

17.1 Definition,Notation and Examples364

17.2 Computing With Turing Machines375

17.3 Adding Multiple Tapes and Nondeterminism382

17.4 Simulating a"Real"Computer393

17.5 Alternative Turing Machine Definitions396

17.6 Encoding Turing Machines as Strings400

17.7 The Universal Turing Machine404

Exercises407

18 The Church-Turing Thesis411

18.1 The Thesis411

18.2 Examples of Equivalent Formalisms414

Exercises424

19 The Unsolvability of the Halting Problem426

19.1 The Language H is Semidecidable but Not Decidable428

19.2 Some Implications of the Undecidability of H431

19.3 Back to Turing,Church,and the Entscheidungsproblem432

Exercises433

20 Decidable and Semidecidable Languages435

20.1 D:The Big Picture435

20.2 SD:The Big Picture435

20.3 Subset Relationships between D and SD437

20.4 The Classes D and SD Under Complement438

20.5 Enumerating a Language440

20.6 Summary444

Exercises445

21 Decidability and Undecidability Proofs448

21.1 Reduction449

21.2 Using Reduction to Show that a Language is Not Decidable452

21.3 Are All Questions About Turing Machines Undecidable?466

2 1.4 Rice's Theorem468

2 1.5 Undecidable Questions About Real Programs472

2 1.6 Showing That a Language is Not Semidecidable474

21.7 Summary of D,SD/D and ？SD Languages that Include Turing Machine Descriptions482

Exercises483

22 Decidability of Languages That Do Not(Obviously)Ask Questions about Turing Machines487

22.1 Diophantine Equations and Hilbert's 10th Problem488

22.2 Post Correspondence Problem489

22.3 Tiling Problems492

22.4 Logical Theories495

22.5 Undecidable Problems about Context-Free Languages499

Exercises508

23 Unrestricted Grammars510

23.1 Definition and Examples510

23.2 Equivalence of Unrestricted Grammars and Turing Machines516

23.3 Grammars Compute Functions518

23.4 Undecidable Problems About Unrestricted Grammars521

23.5 The Word Problem for Semi-Thue Systems522

Exercises524

24 The Chomsky Hierarchy and Beyond526

24.1 The Context-Sensitive Languages526

24.2 The Chomsky Hierarchy539

24.3 Attribute,Feature,and Unification Grammars540

24.4 Lindenmayer Systems544

Exercises553

25 Computable Functions555

25.1 What is a Computable Function?555

25.2 Recursive Function Theory565

25.3 The Recursion Theorem and Its Use573

Exercises580

26 Summary and References581

References582

PART Ⅴ:COMPLEXITY585

27 Introduction to the Analysis of Complexity586

27.1 The Travelina Salesman Problem586

27.2 The Complexity Zoo589

27.3 Characterizing Problems590

27.4 Measuring Time and Space Complexity593

27.5 Growth Rates of Functions597

27.6 Asymptotic Dominance598

27.7 Algorithmic Gaps604

27.8 Examples605

Exercises617

28 Time Complexity Classes621

28.1 The Language Class P621

28.2 The Language Class NP633

28.3 Does P=NP?642

28.4 Using Reduction in Complexity Proofs644

28.5 NP-Completeness and the Cook-Levin Theorem647

28.6 Other NP-Complete Probiems656

28.7 The Relationship between P and NP-Complete672

28.8 The Language Class Co-NP679

28.9 The Time Hierarchy Theorems,EXPTIME,and Beyond681

28.10 The Problem Classes FP and FNP689

Exercises690

29 Space Complexity Classes695

29.1 Analyzing Space Complexity695

29.2 PSPACE,NPSPACE,and Savitch's Theorem699

29.3 PSPACE-Completeness704

29.4 Sublinear Space Complexity713

29.5 The Closure of Space Complexity Classes Under Complement718

29.6 Space Hierarchy Theorems719

Exercises720

30 Practical Solutions for Hard Problems721

30.1 Approaches721

30.2 Randomized Algorithms and the Language Classes BPP,RP,Co-RP and ZPP723

30.3 Heuristic Search731

Exercises740

31 Summary and References742

References742

APPENDICES745

A Review of Mathematical Background:Logic,Sets,Relations,Functions,and Proof Techniques745

A.1 Logic745

A.2 Sets753

A.3 Relations756

A.4 Functions769

A.5 Closures776

A.6 Proof Techniques779

A.7 Reasoning about Programs792

A.8 A General Definition of Closure800

Exercises804

B The Theory:Working with Logical Formulas808

B.1 Working with Boolean Formulas:Normal Forms,Resolution and OBDDs808

B.2 Working with First-Order Formulas:Clause Form and Resolution820

Exercises833

C The Theory:Finite State Machines and Regular Languages835

D The Theory:Context-Free Languages and PDAs839

D.1 Proof of the Greibach Normal Form Theorem839

D.2 Proof that the Deterministic Context-Free Languages are Closed Under Complement846

D.3 Proof of Parikh's Theorem852

E The Theory:Turing Machines and Undecidability856

E.1 Proof that Nondeterminism Does Not Add Power to Turing Machines856

E.2 An Analysis of Iterative Deepening861

E.3 The Power of Reduction862

E.4 The Undecidability of the Post Correspondence Problem864

F The Theory:Complexity869

F.1 Asymptotic Dominance869

F.2 The Linear Speedup Theorem875

APPENDICES G-Q:APPLICATIONS:879

G Applications:Programming Languages and Compilers880

G.1 Defining the Syntax of Programming Languages880

G.2 Are Programming Languages Context-Free?883

G.3 Designing Programming Languages and Their Grammars885

G.4 Compilers for Programming Languages887

G.5 Functional Programming and the Lambda Calculus890

H Applications:Tools for Programming,Databases and Software Engineering899

H.1 Proving Correctness Properties of Programs and Hardware899

H.2 Statecharts:A Technique for Specifying Complex Systems910

H.3 Model-Based Test Case Generation913

H.4 Reverse Engineering914

H.5 Normal Forms for Data and for Querying Relational Databases916

I Applications:Networks918

1.1 Network Protocols918

1.2 Modeling Networks as Graphs927

1.3 Exploiting Knowledge:The Semantic Web929

J Applications:Security948

J.1 Physical Security Systems as FSMs948

J.2 Computer System Safety949

J.3 Cryptography955

J.4 Hackers and Viruses959

K Applications:Computational Biology962

K.1 A(Very)Short Introduction to Molecular Biology and Genetics962

K.2 The Sequence Matching Problem968

K.3 DNA and Protein Sequence Matching Using the Tools of Regular Languages970

K.4 RNA Sequence Matching and Secondary Structure Prediction Using the Tools of Context-Free Languages975

K.5 Complexity of the Algorithms Used in Computational Biology977

L Applications:Natural Language Processing978

L.1 Morphological Analysis978

L.2 Part of Speech Tagging981

L.3 The Grammar of English983

L.4 Building a Complete NL System998

L.5 Speech Understanding Systems999

M Applications:Artificial Intelligence and Computational Reasoning1004

M.1 The Role of Search1006

M.2 A Logical Foundation for Artificial Intelligence1007

M.3 A Rule-Based Foundation for Artificial Intelligence and Cognition1022

N Applications:Art and Entertainment:Music and Games1028

N.1 Music1028

N.2 Classic Games and Puzzles1034

N.3 Interactive Video Games1046

O Applications:Using Regular Expressions1050

P Applications:Using Finite State Machines and Transducers1054

P.1 Finite State Machines Predate Computers1054

P.2 The Towers of Hanoi:Regular Doesn't Always Mean Tractable1058

P.3 The Arithmetic Logic Unit(ALU)1060

P.4 Controlling a Soccer-Playing Robot1062

Q Applications:Using G rammars1065

Q.1 Describing Artificial Languages Designed for Person/Machine Interaction1066

Q.2 Describing Naturally Occurring Phenomena1071

References1073