Muutke küpsiste eelistusi

Introduction to Languages and the Theory of Computation 4th edition [Pehme köide]

  • Formaat: Paperback / softback, 576 pages, kõrgus x laius x paksus: 236x186x16 mm, kaal: 713 g, Illustrations
  • Ilmumisaeg: 16-Apr-2010
  • Kirjastus: McGraw Hill Higher Education
  • ISBN-10: 0071289429
  • ISBN-13: 9780071289429
Teised raamatud teemal:
  • Pehme köide
  • Hind: 88,29 €*
  • * saadame teile pakkumise kasutatud raamatule, mille hind võib erineda kodulehel olevast hinnast
  • See raamat on trükist otsas, kuid me saadame teile pakkumise kasutatud raamatule.
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Lisa soovinimekirja
Introduction to Languages and the Theory of Computation 4th editionSuurem pilt
  • Formaat: Paperback / softback, 576 pages, kõrgus x laius x paksus: 236x186x16 mm, kaal: 713 g, Illustrations
  • Ilmumisaeg: 16-Apr-2010
  • Kirjastus: McGraw Hill Higher Education
  • ISBN-10: 0071289429
  • ISBN-13: 9780071289429
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780071289429.html
Märksõnad:
Introduction to Languages and the Theory of Computation helps students make the connection between the practice of computing and an understanding of the profound ideas that defines it. The book's organization and the author's ability to explain complex topics clearly make this introduction to the theory of computation an excellent resource for a broad range of upper level students. The author has learned through many years of teaching that the best way to present theoretical concepts is to take advantage of the precision and clarity of mathematical language. In a way that is accessible to students still learning this language, he presents the necessary mathematical tools gently and gradually which provides discussion and examples that make the language intelligible.
Preface vii
Introduction x
Chapter 1 Mathematical Tools and Techniques
1(44)
1.1 Logic and Proofs
1(7)
1.2 Sets
8(4)
1.3 Functions and Equivalence Relations
12(5)
1.4 Languages
17(4)
1.5 Recursive Definitions
21(5)
1.6 Structural Induction
26(19)
Exercises
34(11)
Chapter 2 Finite Automata and the Languages They Accept
45(47)
2.1 Finite Automata: Examples and Definitions
45(9)
2.2 Accepting the Union, Intersection, or Difference of Two Languages
54(4)
2.3 Distinguishing One String from Another
58(5)
2.4 The Pumping Lemma
63(5)
2.5 How to Build a Simple Computer Using Equivalence Classes
68(5)
2.6 Minimizing the Number of States in a Finite Automaton
73(19)
Exercises
77(15)
Chapter 3 Regular Expressions, Nondeterminism, and Kleene's Theorem
92(38)
3.1 Regular Languages and Regular Expressions
92(4)
3.2 Nondeterministic Finite Automata
96(8)
3.3 The Nondeterminism in an NFA Can Be Eliminated
104(6)
3.4 Kleene's Theorem, Part 1
110(4)
3.5 Kleene's Theorem, Part 2
114(16)
Exercises
117(13)
Chapter 4 Context-Free Languages
130(34)
4.1 Using Grammar Rules to Define a Language
130(4)
4.2 Context-Free Grammars: Definitions and More Examples
134(4)
4.3 Regular Languages and Regular Grammars
138(3)
4.4 Derivation Trees and Ambiguity
141(8)
4.5 Simplified Forms and Normal Forms
149(15)
Exercises
154(10)
Chapter 5 Pushdown Automata
164(41)
5.1 Definitions and Examples
164(8)
5.2 Deterministic Pushdown Automata
172(4)
5.3 A PDA from a Given CFG
176(8)
5.4 A CFG from a Given PDA
184(7)
5.5 Parsing
191(14)
Exercises
196(9)
Chapter 6 Context-Free and Non-Context-Free Languages
205(19)
6.1 The Pumping Lemma for Context-Free Languages
205(9)
6.2 Intersections and Complements of CFLs
214(4)
6.3 Decision Problems Involving Context-Free Languages
218(6)
Exercises
220(4)
Chapter 7 Turing Machines
224(41)
7.1 A General Model of Computation
224(5)
7.2 Turing Machines as Language Acceptors
229(5)
7.3 Turing Machines That Compute Partial Functions
234(4)
7.4 Combining Turing Machines
238(5)
7.5 Multitape Turing Machines
243(4)
7.6 The Church-Turing Thesis
247(1)
7.7 Nondeterministic Turing Machines
248(4)
7.8 Universal Turing Machines
252(13)
Exercises
257(8)
Chapter 8 Recursively Enumerable Languages
265(34)
8.1 Recursively Enumerable and Recursive
265(3)
8.2 Enumerating a Language
268(3)
8.3 More General Grammars
271(6)
8.4 Context-Sensitive Languages and the Chomsky Hierarchy
277(6)
8.5 Not Every Language Is Recursively Enumerable
283(16)
Exercises
290(9)
Chapter 9 Undecidable Problems
299(32)
9.1 A Language That Can't Be Accepted, and a Problem That Can't Be Decided
299(5)
9.2 Reductions and the Halting Problem
304(4)
9.3 More Decision Problems Involving Turing Machines
308(6)
9.4 Post's Correspondence Problem
314(7)
9.5 Undecidable Problems Involving Context-Free Languages
321(10)
Exercises
326(5)
Chapter 10 Computable Functions
331(27)
10.1 Primitive Recursive Functions
331(7)
10.2 Quantification, Minimalization, and μ-Recursive Functions
338(6)
10.3 Godel Numbering
344(4)
10.4 All Computable Functions Are μ-Recursive
348(4)
10.5 Other Approaches to Computability
352(6)
Exercises
353(5)
Chapter 11 Introduction to Computational Complexity
358(31)
11.1 The Time Complexity of a Turing Machine, and the Set P
358(5)
11.2 The Set NP and Polynomial Verifiability
363(6)
11.3 Polynomial-Time Reductions and NP-Completeness
369(4)
11.4 The Cook-Levin Theorem
373(5)
11.5 Some Other NP-Complete Problems
378(11)
Exercises
383(6)
Solutions to Selected Exercises 389(36)
Selected Bibliography 425(2)
Index of Notation 427(1)
Index 428