Deze website maakt gebruik van cookies. Klik hier voor meer informatie.X sluit
Uitgebreid zoeken
Boek

Automata And Computability

Automata And Computability - Kozen, Dexter C. - ISBN: 9780387949079
Prijs: € 76,20
Levertijd: 3 tot 4 werkdagen
Bindwijze: Boek, Gebonden
Genre: Informatiekunde
Boekenliefde.nl:
Automata And Computability op boekenliefde.nl
Add to cart

Beschrijving

This book presents an elementary account of finite automata and their properties. Pushdown automata provide a broader class of models and enable the analysis of context-free languages.

Details

Titel: Automata And Computability
auteur: Kozen, Dexter C.
Mediatype: Boek
Bindwijze: Gebonden
Taal: Engels
Aantal pagina's: 400
Uitgever: Springer-verlag New York Inc.
Plaats van publicatie: 01
NUR: Informatiekunde
Collectie: Undergraduate Texts in Computer Science
Afmetingen: 260 x 193 x 28
Gewicht: 958 gr
ISBN/ISBN13: 0387949070
ISBN/ISBN13: 9780387949079
Intern nummer: 1815355

Extra informatie

The aim of this textbook is to provide undergraduate students with an introduction to the basic theoretical models of computability, and to develop some of the model's rich and varied structure. Students who have already some experience with elementary discrete mathematics will find this a well-paced first course, and a number of supplementary chapters introduce more advanced concepts. The first part of the book is devoted to finite automata and their properties. Pushdown automata provide a broader class of models and enable the analysis of context-free languages. In the remaining chapters, Turing machines are introduced and the book culminates in discussions of effective computability, decidability, and Gödel's incompleteness theorems. Plenty of exercises are provided, ranging from the easy to the challenging. As a result, this text will make an ideal first course for students of computer science.

Inhoudsopgave

Preface vii
Lectures 1(298)
Introduction
3(11)
1 Course Roadmap and Historical Perspective
3(4)
2 Strings and Sets
7(7)
Finite Automata and Regular Sets
14(115)
3 Finite Automata and Regular Sets
14(5)
4 More on Regular Sets
19(6)
5 Nondeterministic Finite Automata
25(7)
6 The Subset Construction
32(8)
7 Pattern Matching
40(4)
8 Pattern Matching and Regular Expressions
44(5)
9 Regular Expressions and Finite Automata
49(6)
A Kleene Algebra and Regular Expressions
55(6)
10 Homomorphisms
61(6)
11 Limitations of Finite Automata
67(5)
12 Using the Pumping Lemma
72(5)
13 DFA State Minimization
77(7)
14 A Minimization Algorithm
84(5)
15 Myhill-Nerode Relations
89(6)
16 The Myhill-Nerode Theorem
95(5)
B Collapsing Nondeterministic Automata
100(8)
C Automata on Terms
108(6)
D The Myhill-Nerode Theorem for Term Automata
114(5)
17 Two-Way Finite Automata
119(5)
18 2DFAs and Regular Sets
124(5)
Pushdown Automata and Context-Free Languages
129(77)
19 Context-Free Grammars and Languages
129(6)
20 Balanced Parentheses
135(5)
21 Normal Forms
140(8)
22 The Pumping Lemma for CFLs
148(9)
23 Pushdown Automata
157(7)
E Final State Versus Empty Stack
164(3)
24 PDAs and CFGs
167(5)
25 Simulating NPDAs by CFGs
172(4)
F Deterministic Pushdown Automata
176(5)
26 Parsing
181(10)
27 The Cocke-Kasami-Younger Algorithm
191(7)
G The Chomsky-Schutzenberger Theorem
198(3)
H Parikh's Theorem
201(5)
Turing Machines and Effective Computability
206(93)
28 Turing Machines and Effective Computability
206(9)
29 More on Turing Machines
215(6)
30 Equivalent Models
221(7)
31 Universal Machines and Diagonalization
228(7)
32 Decidable and Undecidable Problems
235(4)
33 Reduction
239(6)
34 Rice's Theorem
245(4)
35 Undecidable Problems About CFLs
249(7)
36 Other Formalisms
256(6)
37 The -Calculus
262(7)
I While Programs
269(5)
J Beyond Undecidability
274(8)
38 Godel's Incompleteness Theorem
282(5)
39 Proof of the Incompleteness Theorem
287(5)
K Godel's Proof
292(7)
Exercises 299(74)
Homework Sets
301(14)
Homework 1
301(1)
Homework 2
302(1)
Homework 3
303(1)
Homework 4
304(2)
Homework 5
306(1)
Homework 6
307(1)
Homework 7
308(1)
Homework 8
309(1)
Homework 9
310(1)
Homework 10
311(1)
Homework 11
312(1)
Homework 12
313(2)
Miscellaneous Exercises
315(36)
Finite Automata and Regular Sets
315(18)
Pushdown Automata and Context-Free Languages
333(7)
Turing Machines and Effective Computability
340(11)
Hints and Solutions
351(22)
Hints for Selected Miscellaneous Exercises
351(6)
Solutions to Selected Miscellaneous Exercises
357(16)
References 373(8)
Notation and Abbreviations 381(8)
Index 389

Winkelvoorraad

Dit product is op dit moment niet op voorraad in een van onze vestigingen.