自动机理论、语言和计算导论

内容简介

本书是一本有关自动机理论、形式语言和计算复杂性的经典著作。第2版出版时，主要供研究生教学使用。由于自动机和语言理论在计算机科学的教育中已成为本科生的主要课程，作者在第2版的基础上作了全面修订。本书（第2版）除了继承原书外看大，内看小的特点外，在内容和风格上都作了很大的调整：降低了数学上的难度，删除了一些应用背景不大的内容，增加了一些在实践中较有影响的例子，把相关内容成功地纳入了本科阶段的教育体系。本书主要内容包括：有限状态自动机，正规语言，正规表达式，上下文无关文法，上下文无关语言，下推自动机，图灵机以及问题的不可解性、难解性和复杂性。每节后都附有练习。本书适合作计算机科学相关专业教学用书。

目录

1?Automata:?The?Methods?and?the?Madness 1.l?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?Aotomata?Theory l.5.1?Alphabets 1.5.2?Strings 1.5.3?Languages 1.5.4?Problems 1.6?Summary?of?Chapter?1 1.7?References?for?Chapter?1 2?Finite?Automata 2.1?An?Informal?Picture?of?Finite?Automata 2.1.l?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?DFA''s 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.l?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?e-NFA 2.5.3?Epsilon-Closures 2.5.4?Extended?Transitions?and?Languages?for?E-NFA''s 2.5.5?Eliminating?e-Transitions 2.5.6?Exercises?for?Section?2.5 2.6?Summary?of?Chapter?2 2.7?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?Regu1ar?expressions 3.l.3?Precedence?of?Regular-expression?Operators 3.1.4?Exercises?for?Section?3.1 3.2?Finite?Automata?and?Regu1ar?expressions 3.2.1?From?DFA''s?to?Regular?expressions 3.2.2?Converting?DFA''s?to?Regular?expressions?by?Eliminating?States 3.2.3?Converting?Regular?expressions?to?Automata 3.2.4?Exercises?for?Section?3.2 3.3?Applications?of?Regular?expressions 3.3.1?Regular?expressions?in?UNIX 3.3.2?Lexical?Ana1ysis 3.3.3?Finding?Patterns?in?Text 3.3.4?Exercises?for?Section?3.3 3.4?Algebraic?Laws?for?Regular?expressions 3.4.1?Associativity?and?Commutativity 3