Contents
Preface
1 Introduction to the Theory of Computation
1.1 Mathematical Preliminaries and Notation
Sets
Functions and Relations
Graphs and Trees
Proof Techniques
1.2 Three Basic Concepts
Languages
Grammars
Automata
1.3 Some Applications*
2 Finite Automata
2.1 Deterministic Finite Accepters
Deterministic Accepters and Transition Graphs
Languages and Dfa's
Regular Languages
2.2 Nondeterministic Finite Accepters
Definition of a Nondeterministic Accepter
Why Nondeterminism?
2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters
2.4 Reduction of the Number of States in Finite Automata*
3 Regular Languages and Regular Grammars
3.1 Regular Expressions