Con tents
Preface
v
Notations
vii
Chapter 0 Introduction
1
0.1 Basics
1
0.1.1 Sets
1
0.1.2 Relations and Functions
8
0.1.3 Graphs and Trees
15
0.1.4 Strings and Languages
18
0.1.5 Boolean Logic
27
0.1.6 Fundamental Proof Techniques
28
0.1.7 Introduction to Grammar
37
Glossary
43
Review Questions
44
Exercises
46
Short Questions and Answers
51
Chapter 1 DFA and NFA
58
1.1 Deterministic Finite Automata (DFA)
58
1.1.1 Automata—What is it?
58
1.1.2 Types of Automaton
58
1.1.3 Definition of Deterministic Finite Automaton
59
1.2 Non-Deterministic Finite Automata (NFA)
70
1.3 Equivalence of NFA and DFA
75
1.4 Regular Expression
80
1.4.1 Regular Languages
80
1.4.2 Regular Expressions
81
1.4.3 Building Regular Expressions
81
1.4.4 Languages Defined by Regular Expressions
82
1.4.5 Regular Expressions to NFA
82
1.4.6 NFAs to Regular Expression
83
1.5 Two-way Finite Automata
88
1.6 Finite Automata with Output
89