Preface to the First Edition To the student To the educator The first edition Feedback to the author Acknowledgments Preface to the Sceond Edition（International） 0 Introduction 0.1 Automata,CompUTABILITY,and Complexity Complexity theory Computability theory 0.2 Mathematical Notions and Terminology Sets Sequemces and tuples Functions and relations Graphs Strings and languges Boolean logic Summary of mathematical terms 0.3 Definitions,Theorems,and Proofs Finding proofs 0.4 Types of Proof Proof by construction Proof by construction Proof by induction Exercises,Problims,and Solutions Part One:Automata and Languages 1 Regular Languages 1.1 Finite Automata Formal definition of afinite automaton Examples of finite automata Formal definition of computation Designign finite automata The regular operations 1.2 Nondeteriminism Formal definition of a nondeterministic finite automaton Equivalence of NFAs and DFAs Closure under the regular operations 1.3 Regular Expressions Formal definition of a regular expression Equivalence with finite automata 1.4 Nonregular Languages The pumping lemma for regulan languages Exercises,Problems,and Solutions 2 Context-Free Languages 2.1 Conetxt-free Grammars Formal definition of a context-free grammar Examples of context-free grammars Designing context-free grammars Ambiguity Chomaky mormal form 2.2 Pushdown Automata Formal definition of a pushdown automaton Examples of pushdown autonata Equivalence wish context-free grammars 2.3 Non-context-free Languages The pumping lemma for context-free languages Exercises,Problems,and Solutions Part Two:Computability Theory Part Three:Computability Theory Selected Bibliography Index
