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