Muutke küpsiste eelistusi

Introduction to Formal Languages and Automata 7th edition [Pehme köide]

5.00/5 (2 hinnangut Goodreads-ist)
,
  • Formaat: Paperback / softback, 572 pages, kaal: 1049 g
  • Ilmumisaeg: 04-Mar-2022
  • Kirjastus: Jones and Bartlett Publishers, Inc
  • ISBN-10: 1284231607
  • ISBN-13: 9781284231601
Teised raamatud teemal:
Introduction to Formal Languages and Automata 7th editionSuurem pilt
  • Formaat: Paperback / softback, 572 pages, kaal: 1049 g
  • Ilmumisaeg: 04-Mar-2022
  • Kirjastus: Jones and Bartlett Publishers, Inc
  • ISBN-10: 1284231607
  • ISBN-13: 9781284231601
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781284231601.html
Märksõnad:
An Introduction to Formal Languages and Automata, Seventh Edition is designed for an introductory course on formal languages, automata, compatibility, and related matters forming what is known as the theory of computation. The text takes a problem-solving approach, in which students' abilities are tested at various levels. The Seventh Edition familiarizes students with the foundations and principles of computer science, teaches material useful in subsequent courses, and strengthens students' ability to carry out formal and rigorous mathematical arguments. Key Features: New Introductory Exercises to bridge concepts to more difficult exercises Chapters 1-14 of the sixth edition, with the new exercises, are now reorganized as Part I: Theory
Preface xi
PART I THEORY
1(392)
1 Introduction to the Theory of Computation
3(36)
1.1 Mathematical Preliminaries and Notation
5(14)
Sets
5(3)
Functions and Relations
8(2)
Graphs and Trees
10(1)
Proof Techniques
11(8)
1.2 Three Basic Concepts
19(13)
Languages
19(3)
Grammars
22(6)
Automata
28(4)
1.3 Some Applications*
32(7)
2 Finite Automata
39(38)
2.1 Deterministic Finite Accepters
40(13)
Deterministic Accepters and Transition Graphs
41(2)
Languages and Dfa's
43(5)
Regular Languages
48(5)
2.2 Nondeterministic Finite Accepters
53(8)
Definition of a Nondeterministic Accepter
54(4)
Why Nondeterminism?
58(3)
2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters
61(8)
2.4 Reduction of the Number of States in Finite Automata*
69(8)
3 Regular Languages and Regular Grammars
77(30)
3.1 Regular Expressions
78(6)
Formal Definition of a Regular Expression
78(1)
Languages Associated with Regular Expressions
79(5)
3.2 Connection Between Regular Expressions and Regular Languages
84(13)
Regular Expressions Denote Regular Languages
84(3)
Regular Expressions for Regular Languages
87(6)
Regular Expressions for Describing Simple Patterns
93(4)
3.3 Regular Grammars
97(10)
Right- and Left-Linear Grammars
97(2)
Right-Linear Grammars Generate Regular Languages
99(2)
Right-Linear Grammars for Regular Languages
101(2)
Equivalence of Regular Languages and Regular Grammars
103(4)
4 Properties of Regular Languages
107(30)
4.1 Closure Properties of Regular Languages
108(12)
Closure under Simple Set Operations
108(3)
Closure under Other Operations
111(9)
4.2 Elementary Questions about Regular Languages
120(3)
4.3 Identifying Nonregular Languages
123(14)
Using the Pigeonhole Principle
124(1)
A Pumping Lemma
125(12)
5 Context-Free Languages
137(28)
5.1 Context-Free Grammars
138(11)
Examples of Context-Free Languages
139(2)
Leftmost and Rightmost Derivations
141(1)
Derivation Trees
142(3)
Relation Between Sentential Forms and Derivation Trees
145(4)
5.2 Parsing and Ambiguity
149(11)
Parsing and Membership
149(5)
Ambiguity in Grammars and Languages
154(6)
5.3 Context-Free Grammars and Programming Languages
160(5)
6 Simplification of Context-Free Grammars and Normal Forms
165(28)
6.1 Methods for Transforming Grammars
166(16)
A Useful Substitution Rule
167(2)
Removing Useless Productions
169(4)
Removing λ-Productions
173(2)
Removing Unit-Productions
175(7)
6.2 Two Important Normal Forms
182(7)
Chomsky Normal Form
182(3)
Greibach Normal Form
185(4)
6.3 A Membership Algorithm for Context-Free Grammars*
189(4)
7 Pushdown Automata
193(34)
7.1 Nondeterministic Pushdown Automata
194(10)
Definition of a Pushdown Automaton
195(3)
The Language Accepted by a Pushdown Automaton
198(6)
7.2 Pushdown Automata and Context-Free Languages
204(12)
Pushdown Automata for Context-Free Languages
204(5)
Context-Free Grammars for Pushdown Automata
209(7)
7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages
216(5)
7.4 Grammars for Deterministic Context-Free Languages*
221(6)
8 Properties of Context-Free Languages
227(20)
8.1 Two Pumping Lemmas
228(9)
A Pumping Lemma for Context-Free Languages
228(5)
A Pumping Lemma for Linear Languages
233(4)
8.2 Closure Properties and Decision Algorithms for Context-Free Languages
237(10)
Closure of Context-Free Languages
238(4)
Some Decidable Properties of Context-Free Languages
242(5)
9 Turing Machines
247(28)
9.1 The Standard Turing Machine
248(18)
Definition of a Turing Machine
248(7)
Turing Machines as Language Accepters
255(3)
Turing Machines as Transducers
258(8)
9.2 Combining Turing Machines for Complicated Tasks
266(5)
9.3 Turing's Thesis
271(4)
10 Other Models of Turing Machines
275(26)
10.1 Minor Variations on the Turing Machine Theme
276(8)
Equivalence of Classes of Automata
276(1)
Turing Machines with a Stay-Option
277(2)
Turing Machines with Semi-Infinite Tape
279(2)
The Off-Line Turing Machine
281(3)
10.2 Turing Machines with More Complex Storage
284(5)
Multitape Turing Machines
284(3)
Multidimensional Turing Machines
287(2)
10.3 Nondeterministic Turing Machines
289(3)
10.4 A Universal Turing Machine
292(5)
10.5 Linear Bounded Automata
297(4)
11 A Hierarchy of Formal Languages and Automata
301(24)
11.1 Recursive and Recursively Enumerable Languages
302(7)
Languages That Are Not Recursively Enumerable
304(1)
A Language That Is Not Recursively Enumerable
305(2)
A Language That Is Recursively Enumerable but Not Recursive
307(2)
11.2 Unrestricted Grammars
309(6)
11.3 Context-Sensitive Grammars and Languages
315(6)
Context-Sensitive Languages and Linear Bounded Automata
316(2)
Relation Between Recursive and Context-Sensitive Languages
318(3)
11.4 The Chomsky Hierarchy
321(4)
12 Limits of Algorithmic Computation
325(26)
12.1 Some Problems That Cannot Be Solved by Turing Machines
326(9)
Computability and Decidability
326(1)
The Turing Machine Halting Problem
327(4)
Reducing One Undecidable Problem to Another
331(4)
12.2 Undecidable Problems for Recursively Enumerable Languages
335(4)
12.3 The Post Correspondence Problem
339(6)
12.4 Undecidable Problems for Context-Free Languages
345(3)
12.5 A Question of Efficiency
348(3)
13 Other Models of Computation
351(20)
13.1 Recursive Functions
353(9)
Primitive Recursive Functions
354(4)
Ackermann's Function
358(1)
μ Recursive Functions
359(3)
13.2 Post Systems
362(4)
13.3 Rewriting Systems
366(5)
Matrix Grammars
366(1)
Markov Algorithms
367(2)
L-Systems
369(2)
14 An Overview of Computational Complexity
371(22)
14.1 Efficiency of Computation
372(2)
14.2 Turing Machine Models and Complexity
374(4)
14.3 Language Families and Complexity Classes
378(3)
14.4 The Complexity Classes P and NP
381(2)
14.5 Some NP Problems
383(3)
14.6 Polynomial-Time Reduction
386(3)
14.7 NP-Completeness and an Open Question
389(4)
PART II APPLICATIONS
393(106)
15 Compilers and Parsing
395(28)
15.1 Compilers
396(8)
15.2 Top-Down vs. Bottom-Up Parsing
404(5)
15.3 FIRST Function
409(7)
15.4 FOLLOW Function
416(7)
16 Ll Parsing
423(18)
16.1 Context-Free Grammar Conversion to Nondeterministic Pushdown Automaton
424(5)
Pushdown Automata for LL Parsing
424(1)
Algorithm to Convert Context-Free Grammar to NPDA for LL Parsing
424(5)
16.2 LL(1) Parse Table
429(2)
LL(1) Parse Table
429(2)
16.3 LL(1) Parsing Algorithm
431(4)
LL(1) Parsing Algorithm
432(3)
16.4 LL{k) Parsing
435(6)
17 Lr Parsing
441(58)
17.1 Context-Free Grammar Conversion to NPDA
443(6)
Algorithm to Convert Context-Free Grammar to NPDA for LR Parsing
443(6)
17.2 Items and Closure
449(4)
17.3 DFA Models the LR Parsing Stack
453(14)
Algorithm to Build DFA Modeling LR Parsing
454(13)
17.4 LR(1) Parse Table
467(8)
LR(1) Parsing Actions
468(1)
LR(1) Parse Table Algorithm
468(7)
17.5 LR{1) Parsing Algorithm
475(6)
LR(1) Parsing Algorithm
476(5)
17.6 LR(1) Parsing with A-Productions
481(11)
17.7 LR(1) Parsing Conflicts
492(7)
APPENDIX A FINITE-STATE TRANSDUCERS
499(18)
A.1 A General Framework
499(1)
A.2 Mealy Machines
500(2)
A.3 Moore Machines
502(2)
A.4 Moore and Mealy Machine Equivalence
504(4)
A.5 Mealy Machine Minimization
508(5)
A.6 Moore Machine Minimization
513(1)
A.7 Limitations of Finite-State Transducers
514(3)
APPENDIX B JFLAP: A USEFUL TOOL
517(58)
Answers: Solutions and Hints for Selected Exercises
519(54)
References for Further Reading
573(2)
Index 575
Peter Linz, Professor Emeritus, University of California, Davis Peter Linz is Professor Emeritus in the Department of Computer Science at the University of California, Davis.'Linz received his Ph.D. from the University of Wisconsin.'Professor Linz's research emphasizes the development of a theory of numerical analysis that can be used in the construction of reliable numerical methods used in the design of problem-solving environments for scientific computing.'Linz has released the seventh edition of An Introduction to Formal Languages and Automata, as well as Exploring Numerical Methods: An Introduction to Scientific Computing.'

Susan H. Rodger is Professor of the Practice of Computer Science at Duke University. She received her Ph.D. in Computer Science from Purdue University. Rodger works in the area of computer science education. Her major contributions are in visualization and interaction software for education in theoretical computer science, computing in K-12 and peer-led team learning. Rodger developed JFLAP, software for experimenting with formal languages and automata. JFLAP is the leading educational tool for formal languages and automata theory and has been used around the world for over thirty years in several types of courses including formal languages and automata, compilers, artificial intelligence, and discrete mathematics. Rodger is a leader in integrating computing into K-12 with the Adventures in Alice Programming project. Rodger received the IEEE Computer Society 2019 Taylor L. Booth Education Award, ACM 2013 Karl V. Karlstrom Outstanding Educator Award, Duke University Trinity College 2019 David and Janet Vaughn Brooks Distinguished Teaching Award, and she was one of two finalist candidates for the NEEDS Premier Award for Excellence in Engineering Education Courseware for the software JFLAP.