2.5.1 Chomsky Normal Form (CNF)
142
2.5.2 Greibach Normal Form (GNF)
148
Glossary
149
Review Questions
149
Exercises
150
Short-Questions and Answers
153
Chapter 3 Pushdown Automata
159
3.1 Definitions
159
3.1.1 Nondeterministic PDA (Definition)
159
3.1.2 Transition Functions for NPDA
160
3.1.3 Drawing NPDAs
161
3.1.4 Execution of NPDA
162
3.1.5 Accepting Strings with an NPDA
162
3.1.6 An Example of NPDA Execution
163
3.1.7 Accepting Strings with NPDA (Formal Version)
164
3.2 Relationship between PDA and Context Free
Languages
166
3.2.1 Simplifying CFGs
166
3.2.2 Normal Forms of Context-Free Grammars
167
3.2.3 CFG to NPDA
167
3.2.4 NPDA to CFG
169
3.2.5 Deterministic Pushdown Automata
170
3.3 Properties of Context Free Languages
170
3.3.1 Pumping Lemma for CFG
170
3.3.2 Definitions
171
3.3.3 Proof of Pumping Lemma
171
3.3.4 Usage of Pumping Lemma
173
3.4 Decision Algorithms
176
Glossary
179
Review Questions
180
Exercise
181
Short Questions and Answers
182
Chapter 4 Turing Machines
186
4.1 Turing Machine Model
186
4.1.1 What is a Turing Machine?
186
4.1.2 Definition of Turing Machines
186
4.1.3 Transition Function, Instantaneous Description
and Moves
187
4.1.4 Programming a Turing Machine
188
4.1.5 Turing Machines as Acceptors
188
4.1.6 How to Recognize a Language
188
4.1.7 Turing Machines as Transducers
189
Contents
xi