实例介绍
【实例简介】
【实例截图】
【核心代码】
C O N T E N T vi CONTENTS Part One: Automata and Languages 29 1 Regular Languages 31 1.1 Finite Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Formal definition of a finite automaton . . . . . . . . . . . . . 35 Examples of finite automata . . . . . . . . . . . . . . . . . . . . 37 Formal definition of computation . . . . . . . . . . . . . . . . 40 Designing finite automata . . . . . . . . . . . . . . . . . . . . . 41 The regular operations . . . . . . . . . . . . . . . . . . . . . . 44 1.2 Nondeterminism . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Formal definition of a nondeterministic finite automaton . . . . 53 Equivalence of NFAs and DFAs . . . . . . . . . . . . . . . . . 54 Closure under the regular operations . . . . . . . . . . . . . . . 58 1.3 Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . 63 Formal definition of a regular expression . . . . . . . . . . . . 64 Equivalence with finite automata . . . . . . . . . . . . . . . . . 66 1.4 Nonregular Languages . . . . . . . . . . . . . . . . . . . . . . . . 77 The pumping lemma for regular languages . . . . . . . . . . . 77 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 82 2 Context-Free Languages 101 2.1 Context-Free Grammars . . . . . . . . . . . . . . . . . . . . . . . 102 Formal definition of a context-free grammar . . . . . . . . . . 104 Examples of context-free grammars . . . . . . . . . . . . . . . 105 Designing context-free grammars . . . . . . . . . . . . . . . . 106 Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Chomsky normal form . . . . . . . . . . . . . . . . . . . . . . 108 2.2 Pushdown Automata . . . . . . . . . . . . . . . . . . . . . . . . . 111 Formal definition of a pushdown automaton . . . . . . . . . . . 113 Examples of pushdown automata . . . . . . . . . . . . . . . . . 114 Equivalence with context-free grammars . . . . . . . . . . . . . 117 2.3 Non-Context-Free Languages . . . . . . . . . . . . . . . . . . . . 125 The pumping lemma for context-free languages . . . . . . . . . 125 2.4 Deterministic Context-Free Languages . . . . . . . . . . . . . . . 130 Properties of DCFLs . . . . . . . . . . . . . . . . . . . . . . . 133 Deterministic context-free grammars . . . . . . . . . . . . . . 135 Relationship of DPDAs and DCFGs . . . . . . . . . . . . . . . 146 Parsing and LR(k) Grammars . . . . . . . . . . . . . . . . . . . 151 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 154 Part Two: Computability Theory 163 3 The Church–Turing Thesis 165 3.1 Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Formal definition of a Turing machine . . . . . . . . . . . . . . 167 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. CONTENTS vii Examples of Turing machines . . . . . . . . . . . . . . . . . . . 170 3.2 Variants of Turing Machines . . . . . . . . . . . . . . . . . . . . . 176 Multitape Turing machines . . . . . . . . . . . . . . . . . . . . 176 Nondeterministic Turing machines . . . . . . . . . . . . . . . . 178 Enumerators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 Equivalence with other models . . . . . . . . . . . . . . . . . . 181 3.3 The Definition of Algorithm . . . . . . . . . . . . . . . . . . . . 182 Hilbert’s problems . . . . . . . . . . . . . . . . . . . . . . . . . 182 Terminology for describing Turing machines . . . . . . . . . . 184 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 187 4 Decidability 193 4.1 Decidable Languages . . . . . . . . . . . . . . . . . . . . . . . . . 194 Decidable problems concerning regular languages . . . . . . . 194 Decidable problems concerning context-free languages . . . . . 198 4.2 Undecidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 The diagonalization method . . . . . . . . . . . . . . . . . . . 202 An undecidable language . . . . . . . . . . . . . . . . . . . . . 207 A Turing-unrecognizable language . . . . . . . . . . . . . . . . 209 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 210 5 Reducibility 215 5.1 Undecidable Problems from Language Theory . . . . . . . . . . 216 Reductions via computation histories . . . . . . . . . . . . . . . 220 5.2 A Simple Undecidable Problem . . . . . . . . . . . . . . . . . . . 227 5.3 Mapping Reducibility . . . . . . . . . . . . . . . . . . . . . . . . 234 Computable functions . . . . . . . . . . . . . . . . . . . . . . . 234 Formal definition of mapping reducibility . . . . . . . . . . . . 235 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 239 6 Advanced Topics in Computability Theory 245 6.1 The Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . 245 Self-reference . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 Terminology for the recursion theorem . . . . . . . . . . . . . 249 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 6.2 Decidability of logical theories . . . . . . . . . . . . . . . . . . . 252 A decidable theory . . . . . . . . . . . . . . . . . . . . . . . . . 255 An undecidable theory . . . . . . . . . . . . . . . . . . . . . . . 257 6.3 Turing Reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . 260 6.4 A Definition of Information . . . . . . . . . . . . . . . . . . . . . 261 Minimal length descriptions . . . . . . . . . . . . . . . . . . . 262 Optimality of the definition . . . . . . . . . . . . . . . . . . . . 266 Incompressible strings and randomness . . . . . . . . . . . . . 267 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 270 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. viii CONTENTS Part Three: Complexity Theory 273 7 Time Complexity 275 7.1 Measuring Complexity . . . . . . . . . . . . . . . . . . . . . . . . 275 Big-O and small-o notation . . . . . . . . . . . . . . . . . . . . 276 Analyzing algorithms . . . . . . . . . . . . . . . . . . . . . . . 279 Complexity relationships among models . . . . . . . . . . . . . 282 7.2 The Class P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Polynomial time . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Examples of problems in P . . . . . . . . . . . . . . . . . . . . 286 7.3 The Class NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 Examples of problems in NP . . . . . . . . . . . . . . . . . . . 295 The P versus NP question . . . . . . . . . . . . . . . . . . . . 297 7.4 NP-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 Polynomial time reducibility . . . . . . . . . . . . . . . . . . . 300 Definition of NP-completeness . . . . . . . . . . . . . . . . . . 304 The Cook–Levin Theorem . . . . . . . . . . . . . . . . . . . . 304 7.5 Additional NP-complete Problems . . . . . . . . . . . . . . . . . 311 The vertex cover problem . . . . . . . . . . . . . . . . . . . . . 312 The Hamiltonian path problem . . . . . . . . . . . . . . . . . 314 The subset sum problem . . . . . . . . . . . . . . . . . . . . . 319 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 322 8 Space Complexity 331 8.1 Savitch’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 333 8.2 The Class PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . 336 8.3 PSPACE-completeness . . . . . . . . . . . . . . . . . . . . . . . 337 The TQBF problem . . . . . . . . . . . . . . . . . . . . . . . . 338 Winning strategies for games . . . . . . . . . . . . . . . . . . . 341 Generalized geography . . . . . . . . . . . . . . . . . . . . . . 343 8.4 The Classes L and NL . . . . . . . . . . . . . . . . . . . . . . . . 348 8.5 NL-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . 351 Searching in graphs . . . . . . . . . . . . . . . . . . . . . . . . 353 8.6 NL equals coNL . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 356 9 Intractability 363 9.1 Hierarchy Theorems . . . . . . . . . . . . . . . . . . . . . . . . . 364 Exponential space completeness . . . . . . . . . . . . . . . . . 371 9.2 Relativization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 Limits of the diagonalization method . . . . . . . . . . . . . . 377 9.3 Circuit Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 379 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 388 10 Advanced Topics in Complexity Theory 393 10.1 Approximation Algorithms . . . . . . . . . . . . . . . . . . . . . 393 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. CONTENTS ix 10.2 Probabilistic Algorithms . . . . . . . . . . . . . . . . . . . . . . . 396 The class BPP . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 Primality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 Read-once branching programs . . . . . . . . . . . . . . . . . . 404 10.3 Alternation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 Alternating time and space . . . . . . . . . . . . . . . . . . . . 410 The Polynomial time hierarchy . . . . . . . . . . . . . . . . . . 414 10.4 Interactive Proof Systems . . . . . . . . . . . . . . . . . . . . . . 415 Graph nonisomorphism . . . . . . . . . . . . . . . . . . . . . . 415 Definition of the model . . . . . . . . . . . . . . . . . . . . . . 416 IP = PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 10.5 Parallel Computation . . . . . . . . . . . . . . . . . . . . . . . . 427 Uniform Boolean circuits . . . . . . . . . . . . . . . . . . . . . 428 The class NC . . . . . . . . . . . . . . . . . . . . . . . . . . . 430 P-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . 432 10.6 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 Secret keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 Public-key cryptosystems . . . . . . . . . . . . . . . . . . . . . 435 One-way functions . . . . . . . . . . . . . . . . . . . . . . . . . 435 Trapdoor functions . . . . . . . . . . . . . . . . . . . . . . . . 437 Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . 439 Selected Bibliography 443 Index 448
标签：
Introduction to the Theory of Computation by Michael Sipser, Third Edition, Course Technology.pdf
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论