vi ~ Contents
189
190
196
199
201
6.3 Simplification of Context-free Grammars
6.3.1 Construction of Reduced Grammars
6.3.2 Elimination of Null Productions
6.3.3 Elimination of Unit Productions
6.4 Normal Forms for Context-free Grammars
6.4.1 Chomsky Normal Form
201
6.4.2 Greibach Normal Form
206
6.5 Pumping Lemma for Context-free Languages
6.6 Decision Algorithms for Context-free Languages
6.7 Supplementary Examples
218
Self-Test
223
Exercises
224
213
217
7. PUSHDOWN AUTOMATA
227-266
7.1 Basic Definitions
227
7.2 Acceptance by pda
233
7.3 Pushdown Automata and Context-free Languages
240
7.4 Parsing and Pushdown Automata
251
7.4.1 Top-down Parsing
252
7.4.2 Top-down Parsing Using Deterministic pda's
256
7.4.3 Bottom-up Parsing
258
7.5 Supplementary Examples
260
Sell Test
264
Exercises
265
8. LR(k) GRAMMARS
8.1 LR(k) Grammars
267
8.2 Properties of LR(k) Grammars
8.3 Closure Properties of Languages
8.4 Supplementary Examples
272
Self-Test
273
Erercises
274
270
272
267-276
9. TURING MACHINES AND LINEAR BOUNDED
AUTOMATA
277-308
9.1 Turing Machine Model
278
9.2 Representation of Turing Machines
279
9.2.1 Representation by Instantaneous Descriptions
279
9.2.2 Representation by Transition Table
280
9.2.3 Representation by Transition Diagram
281
9.3 Language Acceptability by Turing Machines
283
9.4 Design of Turing Machines
284
9.5 Description of Turing Machines
289
http://engineeringbooks.net