search for books and compare prices
Tables of Contents for Introduction to Formal Languages and Automata
Chapter/Section Title
Page #
Page Count
Introduction to the Theory of Computation
1
36
Mathematical Preliminaries and Notation
3
11
Sets
3
2
Functions and Relations
5
2
Graphs and Trees
7
2
Proof Techniques
9
3
Exercises
12
2
Three Basic Concepts
14
15
Languages
14
5
Grammars
19
6
Automata
25
1
Exercises
26
3
Some Applications
29
8
Exercises
33
4
Finite Automata
37
36
Deterministic Finite Accepters
37
13
Deterministic Accepters and Transition Graphs
38
2
Languages and Dfa's
40
5
Regular Languages
45
2
Exercises
47
3
Nondeterministic Finite Accepters
50
7
Definition of a Nondeterministic Accepter
50
5
Why Nondeterminism?
55
1
Exercises
56
1
Equivalence of Deterministic and Nondeterministic Finite Accepters
57
8
Exercises
64
1
Reduction of the Number of States in Finite Automata
65
8
Exercises
71
2
Regular Languages and Regular Grammars
73
28
Regular Expressions
73
6
Formal Definition of a Regular Expression
74
1
Languages Associated with Regular Expressions
74
3
Exercises
77
2
Connection Between Regular Expressions and Regular Languages
79
11
Regular Expressions Denote Regular Languages
80
3
Regular Expressions for Regular Languages
83
3
Regular Expressions for Describing Simple Patterns
86
2
Exercises
88
2
Regular Grammars
90
11
Right-and Left-Linear Grammars
91
1
Right-Linear Grammars Generate Regular Languages
92
3
Right-Linear Grammars for Regular Languages
95
2
Equivalence Between Regular Languages and Regular Grammars
97
2
Exercises
99
2
Properties of Regular Languages
101
28
Closure Properties of Regular Languages
102
12
Closure under Simple Set Operations
102
3
Closure under Other Operations
105
6
Exercises
111
3
Elementary Questions About Regular Languages
114
3
Exercises
116
1
Identifying Nonregular Languages
117
12
Using the Pigeonhole Principle
117
1
A Pumping Lemma
118
7
Exercises
125
4
Context-Free Languages
129
26
Context-Free Grammars
130
10
Examples of Context-Free Languages
131
2
Leftmost and Rightmost Derivations
133
1
Derivation Trees
134
2
Relation Between Sentential Forms and Derivation Trees
136
2
Exercises
138
2
Parsing and Ambiguity
140
11
Parsing and Membership
140
5
Ambiguity in Grammars and Languages
145
5
Exercises
150
1
Context-Free Grammars and Programming Languages
151
4
Exercises
153
2
Simplification of Context-Free Grammars and Normal Forms
155
26
Methods for Transforming Grammars
156
15
A Useful Substitution Rule
156
3
Removing Useless Productions
159
4
Removing λ-Productions
163
2
Removing Unit-Productions
165
3
Exercises
168
3
Two Important Normal Forms
171
7
Chomsky Normal Form
171
4
Greibach Normal Form
175
1
Exercises
176
2
A Membership Algorithm for Context-Free Grammars
178
3
Exercises
180
1
Pushdown Automata
181
30
Nondeterministic Pushdown Automata
182
8
Definition of a Pushdown Automaton
182
3
The Language Accepted by a Pushdown Automaton
185
3
Exercises
188
2
Pushdown Automata and Context-Free Languages
190
11
Pushdown Automata for Context-Free Languages
190
5
Context-Free Grammars for Pushdown Automata
195
5
Exercises
200
1
Deterministic Pushdown Automata and Deterministic Context-Free Languages
201
5
Exercises
205
1
Grammars for Deterministic Context-Free Languages
206
5
Exercises
210
1
Properties of Context-Free Languages
211
18
Two Pumping Lemmas
211
8
A Pumping Lemma for Context-Free Languages
212
4
A Pumping Lemma for Linear Languages
216
2
Exercises
218
1
Closure Properties and Decision Algorithms for Context-Free Languages
219
10
Closure of Context-Free Languages
220
5
Some Decidable Properties of Context-Free Languages
225
2
Exercises
227
2
Turing Machines
229
28
The Standard Turing Machine
230
16
Definition of a Turing Machine
230
7
Turing Machines as Language Accepters
237
4
Turing Machines as Transducers
241
3
Exercises
244
2
Combining Turing Machines for Complicated Tasks
246
6
Exercises
251
1
Turing's Thesis
252
5
Exercises
256
1
Other Models of Turing Machines
257
28
Minor Variations on the Turing Machine Theme
258
9
Equivalence of Classes of Automata
258
2
Turing Machines with a Stay-Option
260
2
Turing Machines with Semi-Infinite Tape
262
1
The Off-Line Turing Machine
263
2
Exercises
265
2
Turing Machines With More Complex Storage
267
5
Multitape Turing Machines
267
3
Multidimensional Turing Machines
270
1
Exercises
271
1
Nondeterministic Turing Machines
272
4
Exercises
275
1
A Universal Turing Machine
276
5
Exercises
280
1
Linear Bounded Automata
281
4
Exercises
284
1
A Hierarchy of Formal Languages and Automata
285
26
Recursive and Recursively Enumerable Languages
286
8
Languages That Are Not Recursively Enumerable
288
2
A Language That Is Not Recursively Enumerable
290
1
A Language That Is Recursively Enumerable But Not Recursive
291
2
Exercises
293
1
Unrestricted Grammars
294
6
Exercises
299
1
Context-Sensitive Grammars and Languages
300
7
Context-Sensitive Languages and Linear Bounded Automata
301
3
Relation Between Recursive and Context-Sensitive Languages
304
2
Exercises
306
1
The Chomsky Hierarchy
307
4
Exercises
309
2
Limits of Algorithmic Computation
311
26
Some Problems that Cannot be Solved by Turing Machines
312
9
Computability and Decidability
312
1
The Turing Machine Halting Problem
313
4
Reducing One Undecidable Problem to Another
317
3
Exercises
320
1
Undecidable Problems for Recursively Enumerable Languages
321
4
Exercises
324
1
The Post Correspondence Problem
325
7
Exercises
331
1
Undecidable Problems for Context-Free Languages
332
5
Exercises
335
2
Other Models of Computation
337
2
Recursive Functions
339
9
Primitive Recursive Functions
340
4
Ackermann's Functions
344
1
μ-Recursive Functions
345
2
Exercises
347
1
Post Systems
348
4
Exercises
351
1
Rewriting Systems
352
1
Matrix Grammars
352
1
Markov Algorithms
353
2
L-Systems
355
1
Exercises
356
An Introduction to Computational Complexity
257
115
Efficiency of Computation
358
3
Exercises
360
1
Turing Machines and Complexity
361
3
Exercises
364
1
Language Families and Complexity Classes
364
4
Exercises
368
1
The Complexity Classes P and NP
368
4
Exercises
371
1
References for Further Reading
372
1
Index
373