2.1.4 The Entire System as an Automaton............ 43

2.1.5 Using the Product Automaton to Vahdate the Protocol . 45

2.2 Deterministic Finite Automata................... 45

2.2.1 Definition of a Deterministic Finite Automaton...... 46

2.2.2 How a DFA Processes Strings................ 46

2.2.3 Simpler Notations for DFAs ................ 48

2.2.4 Extending the Transition Function to Strings....... 49

2.2.5 The Language of a DFA................... 52

2.2.6 Exercises for Section 2.2................... 53

2.3 Nondeterministic Finite Automata................. 55

2.3.1 An Informal View of Nondeterministic Finite Automata . 56

2.3.2 Definition of Nondeterministic Finite Automata...... 57

2.3.3 The Extended Transition Function............. 58

2.3.4 The Language of an NFA.................. 59

2.3.5 Equivalence of Deterministic and Nondeterministic Finite Automata........................... 60

2.3.6 A Bad Case for the Subset Construction.......... 65

2.3.7 Exercises for Section 2.3................... 66

2.4 An Application: Text Search .................... 68

2.4.1 Finding Strings in Text................... 68

2.4.2 Nondeterministic Finite Automata for Text Search .... 69

2.4.3 A DFA to Recognize a Set of Keywords.......... 70

2.4.4 Exercises for Section 2.4................... 72

2.5 Finite Automata With Epsilon-TVansitions............. 72

2.5.1 Uses of £-Transitions..................... 72

2.5.2 The Formal Notation for an e-NFA............. 74

2.5.3 Epsilon-Closures....................... 75

2.5.4 Extended Transitions and Languages for NFAs..... 76

2.5.5 Ehminating c-Transitions.................. 77

2.5.6 Exercises for Section 2.5................... 80

2.6 Summary of Chapter 2........................ 80

2.7 References for Chapter 2....................... 81

3 Regular Expressions and Languages 83

3.1 Regular Expressions......................... 83

3.1.1 The Operators of Regular Expressions........... 84

3.1.2 Building Regular Expressions................ 85

3.1.3 Precedence of Regular-Expression Operators....... 88

3.1.4 Exercises for Section 3.1................... 89

3.2 Finite Automata and Regular Expressions............. 90

3.2.1 From DFAs to Regular Expressions............ 91

3.2.2 Converting DFAs to Regular Expressions by Ehminating States............................. 96

3.2.3 Converting Regular Expressions to Automata....... 101

3.2.4 Exercises for Section 3.2................... 106

3.3 Applications of Regular Expressions................108

3.3.1 Regular Expressions in UNIX................108

3.3.2 Lexical Analysis .......................109

3.3.3 Finding Patterns in Tsxt ..................Ill

3.3.4 Exercises for Section 3.3...................113

3.4 Algebraic Laws for Regular Expressions..............114

3.4.1 Associativity and Commutativity..............114

3.4.2 Identities and AnnihUators.................115

3.4.3 Distributive Laws.......................115

3.4.4 The Idempotent Law.....................116

3.4.5 Laws Involving Closures...................117

3.4.6 Discovering Laws for Regular Expressions.........117

3.4.7 The Test for a Regular-Expression Algebraic Law.....119

3.4.8 Exercises for Section 3.4...................120

3.5 Summary of Chapter 3........................122

3.6 References for Chapter 3.......................122

4 Properties of Regular Languages 125

4.1 Proving Languages not to be Regular................126

4.1.1 The Pumping Lemma for Regular Languages.......126

4-1.2 Applications of the Pumping Lemma............127

4.1.3 Exercises for Section 4.1...................129

4.2 Closure Properties of Regular Languages..............131

4.2.1 Closure of Regidar Languages Under Boolean Operations 131

4.2.2 Reversal............................137

4.2.3 Homomorphisms.......................139

4.2.4 Inverse Homomorphisms...................140

4.2.5 Exercises for Section 4.2...................145

4.3 Decision Properties of Regular Languages.............149

4.3.1 Converting Among Representations ............149

4.3.2 Tbsting Emptiness of Regular Languages..........151

4.3.3 Testing Membership in a Regular Language........153

4.3.4 Exercises for Section 4.3...................153

4.4 Equivalence and Minimization of Automata............154

4.4.1 Testing Equivalence of States................154

4.4.2 Testing Equivalence of Regular Languages.........157

4.4.3 Minimization of DFAs....................159

4.4.4 Why the Minimized DFA Cant Be Beaten ........162

4.4.5 Exercises for Section 4.4...................164

4.5 Summary of Chapter 4........................165

4.6 References for Chapter 4.......................166

Context-Free Grammars and Languages 169

5.1 Context-Free Grammars.......................169

5.1.1 An Informal Example....................170

5.1.2 Definition of Context-Free Grammars...........171

5.1.3 Derivations Using a Grammar................173

5.1.4 Leftmost and Rightmost Derivations............175

5.1.5 The Language of a Grammar................177

5.1.6 Sentential Forms.......................178

5.1.7 Exercises for Section 5.1...................179

5.2 Parse Trees..............................181

5.2.1 Constructing Parse TVees..................181

5.2.2 The Yield of a Parse Tree..................183

5.2.3 Inference, Derivations, and Parse Trees ..........184

5.2.4 Prom Inferences to Trees...................185

5.2.5 From Trees to Derivations..................187

5.2.6 From Derivations to Recursive Inferences.........190

5.2.7 Exercises for Section 5.2...................191

5.3 AppUcations of Context-Free Grammars..............191

5.3.1 Parsers ............................192

5.3.2 The YACC Parser-Generator................194

5.3.3 Markup Languages......................196

5.3.4 XML and Document-Type Definitions...........198

5.3.5 Exercises for Section 5.3...................204

5.4 Ambiguity in Grammars and Languages..............205

5.4.1 Ambiguous Grammars....................205

5.4.2 Removing Ambiguity From Grammars...........207

5.4.3 Leftmost Derivations as a Way to Express Ambiguity . . 211

5.4.4 Inherent Ambiguity .....................212

5.4.5 Exercises for Section 5.4...................214

5.5 Summary of Chapter 5........................215

5.6 References for Chapter 5.......................216

Pushdown Automata 219

6.1 Definition of the Pushdown Automaton ..............219

6.1.1 Informal Introduction....................219

6.1.2 The Formal Definition of Pushdown Automata......221

6.1.3 A Graphical Notation for PDAs..............223

6.1.4 Instantaneous Descriptions of a PDA............224

6.1.5 Exercises for Section 6.1...................228

6.2 The Languages of a PDA ......................229

6.2.1 Acceptance by Final State..................229

6.2.2 Acceptance by Empty Stack.................230

6.2.3 From Empty Stack to Final State..............231

6.2.4 From Final State to Empty Stack..............234

6.2.5 Exercises for Section 6.2...................236