1.6.1 Definition
89
1.6.2 Mealey Machine
89
1.6.3 Moore Machine
90
1.7 Properties of Regular Sets (Languages)
91
1.7.1 Closure
91
1.7.2 Union, Concatenation, Negation, Kleene Star,
Reverse
92
1.7.3 Intersection and Set Difference
92
1.8 Pumping Lemma
93
1.8.1 Principle of Pumping Lemma
93
1.8.2 Applying the Pumping Lemma
94
1.9 Closure Properties of Regular Languages
96
1.10 Myhill-Nerode Theorem
97
1.10.1 Myhill-Nerode Relations
97
1.10.2 Myhill-Nerode Theorem
98
Glossary
99
Review Questions
99
Exercises
100
Short Questions and Answers
108
Chapter 2 Context-Free Grammars
115
2.1 Introduction
115
2.1.1 Definition of CFG
115
2.1.2 Example of CFG
115
2.1.3 Right-Linear Grammar
115
2.1.4 Right-Linear Grammars and NFAs
116
2.1.5 Left-Linear Grammar
116
2.1.6 Conversion of Left-linear Grammar into
Right-Linear Grammar
117
2.2 Derivation Trees
118
2.2.1 Definition of a Derivation Tree
118
2.2.2 Sentential Form
119
2.2.3 Partial Derivation Tree
119
2.2.4 Right Most/Left Most/Mixed Derivation
119
2.3 Parsing and Ambiguity
127
2.3.1 Parsing
127
2.3.2 Exhaustive Search Parsing
128
2.3.3 Topdown/Bottomup Parsing
128
2.3.4 Ambiguity
129
2.3.5 Ambiguous Grammars/Ambiguous Languages
130
2.4 Simplification of CFG
131
2.4.1 Simplification of CFG-Introduction
131
2.4.2 Abolishing Useless Productions
132
2.5 Normal Forms
142
x
Con tents