Muutke küpsiste eelistusi

E-raamat: Automata and Computability: A Programmer's Perspective [Taylor & Francis e-raamat]

  • Formaat: 328 pages
  • Ilmumisaeg: 30-Sep-2020
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-13: 9781315148175
Teised raamatud teemal:
  • Taylor & Francis e-raamat
  • Hind: 133,87 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
  • Tavahind: 191,24 €
  • Säästad 30%
Automata and Computability: A Programmer's PerspectiveSuurem pilt
  • Formaat: 328 pages
  • Ilmumisaeg: 30-Sep-2020
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-13: 9781315148175
Teised raamatud teemal:
Taylor & Francis e-raamatudRohkem infot Taylor & Francis e-raamatute kohta
Raamatu kodulehekülg: https://www.taylorfrancis.com/books/9781315148175

Automata and Computability is a class-tested textbook which provides a comprehensive and accessible introduction to the theory of automata and computation. The author uses illustrations, engaging examples, and historical remarks to make the material interesting and relevant for students. It incorporates modern/handy ideas, such as derivative-based parsing and a Lambda reducer showing the universality of Lambda calculus. The book also shows how to sculpt automata by making the regular language conversion pipeline available through a simple command interface. A Jupyter notebook will accompany the book to feature code, YouTube videos, and other supplements to assist instructors and students.



Features





  • Uses illustrations, engaging examples, and historical remarks to make the material accessible


  • Incorporates modern/handy ideas, such as derivative-based parsing and a Lambda reducer showing the universality of Lambda calculus


  • Shows how to "sculpt" automata by making the regular language conversion pipeline available through simple command interface


  • Uses a mini functional programming (FP) notation consisting of lambdas, maps, filters, and set comprehension (supported in Python) to convey math through PL constructs that are succinct and resemble math


  • Provides all concepts are encoded in a compact Functional Programming code that will tesselate with Latex markup and Jupyter widgets in a document that will accompany the books. Students can run code effortlessly.


 

Foreword xiii
Preface xv
Acknowledgments xix
1 What Machines Think
3(12)
1.1 Problems Without Algorithms
4(1)
1.2 How to Define a Computer?
5(2)
1.3 Practical Application: Syntax Definition/Checking
7(4)
1.4 Simplified Turing Machines as Parsers
11(2)
1.5 Automata and Computability for Lifelong Learning
13(2)
2 Denning Languages: Patterns in Sets of Strings
15(12)
2.1 Symbol, Alphabet, String, Language
15(3)
2.1.1 Symbol
15(1)
2.1.2 Alphabet
15(1)
2.1.3 String or Word
16(1)
2.1.4 Various Notions of Zero and One
17(1)
2.2 Language
18(7)
2.2.1 Language Concatenation
20(1)
2.2.2 The Zero and One for Language Concatenation
21(1)
2.2.3 Zero and One of Language Concatenation in Python
21(1)
2.2.4 Exponentiation of a Language
22(1)
2.2.5 Python Encoding of Language Exponentiation
23(1)
2.2.6 Union and Intersection of Languages
24(1)
2.3 Useful Results, Slippery Roads
25(2)
3 Kleene Star: Basic Method of Defining Repetitious Patterns
27(14)
3.1 Three Ways to Describe Star
27(1)
3.2 Additional Definitions and Properties of Star
28(3)
3.3 Language Complementation
31(1)
3.4 Other Language Operations
32(1)
3.4.1 Symmetric Difference, Subtraction
32(1)
3.4.2 Reverse of a Language
32(1)
3.5 String/Language Homomorphisms
33(2)
3.5.1 Taking Star Repeatedly
35(1)
3.6 Enumerating Strings in a Language
35(6)
4 Basics of DFA
41(16)
4.1 DFA Everywhere
41(1)
4.2 Elements of a DFA
42(1)
4.3 Formal Structure of DFA
43(1)
4.4 The Language of a DFA
44(1)
4.4.1 DFA as String Classifers
44(1)
4.4.2 Basics of Designing a DFA
45(1)
4.5 Formal Definition of DFA Language Acceptance
45(2)
4.6 "Lasso" Shape of DFA and the Pumping Lemma
47(3)
4.6.1 General Statement of the Pumping Lemma
48(2)
4.7 Proving a Language to Be Non-Regular
50(2)
4.7.1 Why All Splits of x, y, z?
51(1)
4.8 Grossly Abusing the Pumping Lemma
52(2)
4.8.1 Inability to Prove with this Pumping Lemma
53(1)
4.9 Regularity-Preserving Transformations Aid Proofs
54(3)
5 Designing DFA
57(10)
5.1 Understanding the Language to Be Realized
57(2)
5.1.1 The Language of Equal Changes
57(1)
5.1.2 Best Practices to Correct DFA Design and Verification
58(1)
5.2 Examples of Designing DFA
59(5)
5.2.1 The Language of Blocks of 3
59(1)
5.2.2 DFA for "Ends with 0101"
60(1)
5.2.3 DFA for "MSB/LSB-first Binary Number is Divisible by 3"
60(2)
5.2.4 DFA for "Third-last bit is a 1"
62(2)
5.3 Automd: A Markdown Language for All Machines
64(3)
5.3.1 Markdown for DFA
64(3)
6 Operations on DFA
67(14)
6.1 Complementation of DFA
67(1)
6.2 Union and Intersection of DFA
67(4)
6.3 Language Equivalence and Isomorphism
71(1)
6.4 DFA Minimization and Myhill-Nerode Theorem
72(4)
6.4.1 Fully Worked-out Example of DFA Minimization
72(3)
6.4.2 Salient Code Excerpts
75(1)
6.5 Examples of Language Design and Manipulation
76(5)
6.5.1 Use of Union, Minimization, and Language Equivalence
77(1)
6.5.2 Use of DeMorgan's Law
78(3)
7 Nondeterministic Finite Automata
81(14)
7.1 Overview of NFA
81(2)
7.2 Formal Description of NFA
83(1)
7.3 Language of an NFA: Example Driven
84(1)
7.3.1 Simulations of the NFA of Figure 7.5
84(1)
7.3.2 Simulations of the NFA of Figure 7.3
85(1)
7.4 Language of an NFA: via Eclosure
85(2)
7.4.1 Defining Eclosure
86(1)
7.4.2 Definition of δ and δ
86(1)
7.5 NFA to DFA Conversion through Subset Construction
87(3)
7.6 Brzozowski's DFA Minimization Algorithm
90(2)
7.6.1 Reversal of a DFA Yields an NFA
90(2)
7.7 A Complete Illustration of Brzozowski's Minimization
92(3)
8 Regular Expressions and NFA
95(20)
8.1 Regular Expressions
95(1)
8.2 RE to NFA Conversion: Examples, Algorithm Sketch
96(4)
8.3 A More Extensive Example
100(1)
8.4 Regular Expressions: Ubiquitous, yet Error-Prone
101(2)
8.5 Anatomy of the RE to NFA Converter
103(3)
8.6 Example: Designing an Error-Correcting DFA
106(2)
8.6.1 Error-correcting RE for "within Hamming Distance of 2"
106(2)
8.6.2 NFA-based Design of "within Hamming Distance of 2"
108(1)
8.7 Minimal DFA and Isomorphism
108(3)
8.8 DFA Ultimate Periodicity to Solve the Postage Stamp Problem
111(4)
8.8.1 Ultimately periodic sets and lengths of members of a regular language
111(1)
8.8.2 Stamp Problem and Ultimate Periodicity via Jove
112(1)
8.8.3 Applying to numbers that are not relatively prime
113(1)
8.8.4 Solving for three stamps
113(1)
8.8.5 Lengths of strings accepted by DFA
113(2)
9 NFA to RE Conversion
115(12)
9.1 NFA to RE Conversion Algorithm
115(1)
9.2 Illustration on Pedagogical Example
116(2)
9.3 Illustration on Non-trivial Example
118(3)
9.4 Checking the Conversion
121(1)
9.5 DFA, NFA, and RE Are Equally Powerful
122(1)
9.6 Implementation of NFA to RE
123(1)
9.7 Closure Results Pertaining to Regular Languages
123(4)
10 Derivative-Based Regular Expression Matching
127(10)
10.1 Introduction to RE Derivatives
127(2)
10.2 Definitions
129(5)
10.2.1 Derivative Rules
129(3)
10.2.2 Nullability Rules
132(2)
10.3 Implementation of Derivative-Based String Matching
134(3)
10.3.1 Derivatives: Closing Thoughts
134(3)
11 Context-Free Languages and Grammars
137(24)
11.1 Context-Free Language Examples
137(1)
11.2 Context-Free Grammars and Parse Trees
138(2)
11.2.1 Elements of Context-Free Grammars
139(1)
11.2.2 Parse Trees, Language of a CFG
139(1)
11.3 Avoiding Mistakes in Designing CFGs
140(2)
11.3.1 Completeness and Consistency
141(1)
11.4 The Design of CFG, and the Hill/Valley Plot for Arguing Consistency and Completeness
142(2)
11.5 Ambiguous Grammars, and Disambiguation
144(3)
11.5.1 Disambiguation
145(2)
11.5.2 Disambiguation Is Crucial!
147(1)
11.5.3 Impossibility Results
147(1)
11.6 Inherently Ambiguous Languages
147(2)
11.7 Expressing DFA via CFGs
149(3)
11.7.1 Purely Right Linear Grammars
150(1)
11.7.2 Closure, Purely Left Linear, and Mixed Linearity
151(1)
11.8 Historical Importance of the Theory of Parsing
152(2)
11.8.1 Combating Inherent Ambiguity
153(1)
11.9 A Pumping Lemma for CFLs
154(3)
11.9.1 Application of the CFL Pumping Lemma
157(1)
11.10 The Complement of a Non-CFL Can Be a CFL
157(4)
11.10.1 Growing "Inside-Out"
158(3)
12 Pushdown Automata
161(22)
12.1 Pushdown Automaton Basics
161(3)
12.2 Formal Description of PDA
164(1)
12.2.1 Acceptance, Deterministic PDA
165(1)
12.3 Exploring the PDA for LDyck Using Jove
165(2)
12.4 PDA Behavior Through Examples
167(6)
12.4.1 Rerunning pda6 with Larger Stack Allowed
171(2)
12.5 Toward More Practical PDA
173(2)
12.6 CFG to PDA Conversion
175(6)
12.6.1 Disambiguation
179(2)
12.7 Practical Knowledge Imparted by Jove: Three Parsers
181(2)
13 Turing Machines
183(26)
13.1 Brief History of Turing Machines
183(1)
13.2 Universal Computing Devices
184(2)
13.3 Formal Definition of Turing Machines
186(3)
13.4 Examples of Simple TMs
189(4)
13.4.1 A Simple DTM that Flips Bits
189(1)
13.4.2 TMs that check if a string contains 101
189(4)
13.5 A DTM for w#w and an NDTM for ww
193(7)
13.5.1 A DTM Recognizing w#w
193(1)
13.5.2 A Nondeterministic TM Recognizing ww
193(1)
13.5.3 Nondeterminism does not increase a TM's Expressive Power
194(6)
13.6 Example: A TM that Works on the Collatz Problem
200(3)
13.6.1 Markdown for the Collatz Problem TM with Comments
200(3)
13.7 The Chomsky Hierarchy
203(2)
13.7.1 Recursively Enumerable and Recursive Languages
204(1)
13.8 An Alternate Notation for Instantaneous Descriptions
205(4)
14 Interplay between Formal Languages
209(18)
14.1 Why Study Impossibility Results?
209(2)
14.1.1 Definitions: Procedure and Algorithm
209(1)
14.1.2 Formal Languages Associated with Turing Machines
210(1)
14.1.3 Allaying Confusion: Language vs. Language Family
210(1)
14.2 One Example of a Recursive and an RE Language
211(4)
14.2.1 A Recursive Language
211(1)
14.2.2 Prerequisites to Defining the Notion of RE
212(1)
14.2.3 Combining Semi-deciders for L and L
213(1)
14.2.4 The "no wimp" Clause
213(1)
14.2.5 A Recursively Enumerable Language
213(2)
14.3 Other Examples of Recursive and RE Languages
215(4)
14.3.1 RE Languages that are not Recursive
216(1)
14.3.2 Why is it called Recursively Enumerable?
217(1)
14.3.3 Alternate proof of ATM being RE
218(1)
14.3.4 Some More RE Languages
218(1)
14.4 Summary of Decidability/Semi-Decidability Results
219(2)
14.4.1 Existence of Non-RE languages
220(1)
14.5 RE and Recursive Sets: More High-Level Proof Sketches
221(6)
14.5.1 Language of DFA D where L(D) = Σ* is Recursive
221(1)
14.5.2 Language of CFG G where L(G) = Φ is Recursive
222(1)
14.5.3 Language of LBA that halt on input w is Recursive
223(1)
14.5.4 Language of Turing machines whose first output is `3'
224(3)
15 Post Correspondence, and Other Undecidability Proofs
227(14)
15.1 Post Correspondence: "Drosophila" for Decidability
227(2)
15.2 Proof Sketch of the Undecidability of PCP
229(4)
15.2.1 Tile Construction Basics
230(1)
15.2.2 Proving Grammar Ambiguity by Reduction from PCP
231(1)
15.2.3 PCP in Jove
231(2)
15.3 Undecidability of the Acceptance Problem
233(1)
15.4 Halting (HaltTM) is Undecidable
234(2)
15.5 Mapping Reductions
236(5)
15.5.1 Undecidable problems are "ATM in disguise"
239(2)
16 NP-Completeness
241(26)
16.1 What Does NP-Complete Mean?
241(3)
16.1.1 Grouping Problems: Solving One Implies Solving All
242(1)
16.1.2 Some Historical Notes
243(1)
16.2 NPC Notions Defined Based on NDTMs
244(4)
16.2.1 P-time
244(2)
16.2.2 NP-time
246(1)
16.2.3 NP Verifier
246(1)
16.2.4 Examples of P-time and NP-time Deciders
247(1)
16.2.5 Decider versus Verifier Views
247(1)
16.3 Introducing SAT Problems
248(5)
16.3.1 A Warmup: 2-SAT
249(2)
16.3.2 2-SAT: Examples and Algorithm
251(2)
16.4 3-SAT and Its NP-Completeness
253(1)
16.5 3-SAT Is NP-Complete
254(3)
16.5.1 3-SAT is in NP
255(1)
16.5.2 Every Language in NP Reduces to 3-SAT
255(1)
16.5.3 How P=NP is Obtained if 3-SAT P?
256(1)
16.6 Show that Clique Is NPC: Reduction from 3-SAT
257(1)
16.6.1 Clique is in NP
257(1)
16.6.2 Some Language in NPC Reduces to Clique
257(1)
16.7 Complexity Classes, Closing Caveats
258(3)
16.7.1 NP-Hard Problems can be Undecidable (Pitfall in Proofs)
258(2)
16.7.2 The CoNP and CoNPC Complexity Classes
260(1)
16.8 SAT in Practice
261(6)
17 Binary Decision Diagrams as Minimal DFA
267(12)
17.1 Boolean Functions in Computing Theory and Practice
267(1)
17.2 Boolean Functions as Minimal DFA of Their On-Sets
268(3)
17.3 The Importance of Variable Ordering
271(4)
17.3.1 Finding a better input variable order
272(1)
17.3.2 Functions with linearly sized BDDs
273(2)
17.4 From Minimal DFA to BDD: Intuitive Presentation
275(2)
17.5 On BDD Sizes
277(2)
18 Computability Using Lambdas
279(18)
18.1 The History of Lambda Calculus
279(1)
18.2 Lambdas from a Programmer's Perspective
280(2)
18.3 Syntax and Semantics of the Lambda Calculus
282(2)
18.4 Illustration: Church Numerals in Python
284(1)
18.5 Illustration: Booleans, Pairs, Other Functions
284(3)
18.6 Handling Recursion
287(1)
18.7 Obtaining Fixpoints from Fixpoint Equations
288(4)
18.7.1 Y: A Fixpoint Finder
288(1)
18.7.2 The Y Combinator
288(1)
18.7.3 Expression Recursion using Y
289(1)
18.7.4 Reason for an alternate fixpoint finder Ye
290(2)
18.8 Illustrating the Use of Fixpoint Combinators
292(1)
18.9 Combinators
292(5)
Appendices
Appendix A A Recap of Discrete Math
297(6)
A.1 Sets
297(2)
A.1.1 Set Builder
297(1)
A.1.2 Powerset
298(1)
A.1.3 Complement
299(1)
A.1.4 Equivalence Classes, Partitioning
299(1)
A.2 Mathematical Logic
299(1)
A.3 Proof Methods: Using Contrapositive, by Contradiction
300(1)
A.4 Cartesian Product, Binary Relations, Functions
301(1)
A.5 Functions: Signature, Onto, Into, Total
301(1)
A.6 Trees
302(1)
Appendix B Catalog of Jove Functions
303(10)
B.1 Jove's Top-Level Functions
303(7)
B.1.1
Chapters 2 and 3
304(1)
B.1.2
Chapters 4 through 6
305(1)
B.1.3
Chapters 7 through 9
305(1)
B.1.4
Chapter 10
306(1)
B.1.5
Chapter 11
307(1)
B.1.6
Chapter 12
307(1)
B.1.7
Chapter 13
308(1)
B.1.8
Chapter 15
308(1)
B.1.9
Chapters 16 and 17
308(1)
B.1.10
Chapter 18
309(1)
B.2 Jove's Use of Python, Including Lambda Basics
310(3)
Appendix C There Are More Languages than RE Languages
313(6)
C.1 Godel Hash
313(1)
C.2 Cantor-Schroder-Bernstein (CSB) Theorem
314(1)
C.3 Cantor's Diagonalization Proof about Languages
315(1)
C.4 Real | Is Higher than | Nat
316(3)
Selected References 319(4)
Index 323
Ganesh Gopalakrishnan is a professor in the Computer Science Department at the University of Utah.
Püsilink: https://www.kriso.ee/db/9781315148175_pe.html
Märksõnad: