Automata and Computability: A Programmer’s Perspective
- Length: 328 pages
- Edition: 1
- Language: English
- Publisher: Chapman and Hall/CRC
- Publication Date: 2020-09-30
- ISBN-10: 036765654X
- ISBN-13: 9780367656546
- Sales Rank: #9749390 (See Top 100 Books)
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.
- All the code can be accessed: https://github.com/ganeshutah/Jove.git/.
Cover Half Title Title Page Copyright Page Table of Contents Foreword Preface Acknowledgments 1: What Machines Think 1.1 Problems Without Algorithms 1.2 How to Define a Computer? 1.3 Practical Application: Syntax Definition/Checking 1.4 Simplified Turing Machines as Parsers 1.5 Automata and Computability for Lifelong Learning 2: Defining Languages: Patterns in Sets of Strings 2.1 Symbol, Alphabet, String, Language 2.1.1 Symbol 2.1.2 Alphabet 2.1.3 String or Word 2.1.4 Various Notions of Zero and One 2.2 Language 2.2.1 Language Concatenation 2.2.2 The Zero and One for Language Concatenation 2.2.3 Zero and One of Language Concatenation in Python 2.2.4 Exponentiation of a Language 2.2.5 Python Encoding of Language Exponentiation 2.2.6 Union and Intersection of Languages 2.3 Useful Results, Slippery Roads 3: Kleene Star: Basic Method of Defining Repetitious Patterns 3.1 Three Ways to Describe Star 3.2 Additional Definitions and Properties of Star 3.3 Language Complementation 3.4 Other Language Operations 3.4.1 Symmetric Difference, Subtraction 3.4.2 Reverse of a Language 3.5 String/Language Homomorphisms 3.5.1 Taking Star Repeatedly 3.6 Enumerating Strings in a Language 4: Basics of DFA 4.1 DFA Everywhere 4.2 Elements of a DFA 4.3 Formal Structure of DFA 4.4 The Language of a DFA 4.4.1 DFA as String Classifers 4.4.2 Basics of Designing a DFA 4.5 Formal Definition of DFA Language Acceptance 4.6 “Lasso” Shape of DFA and the Pumping Lemma 4.6.1 General Statement of the Pumping Lemma 4.7 Proving a Language to Be Non-Regular 4.7.1 Why All Splits of x, y, z? 4.8 Grossly Abusing the Pumping Lemma 4.8.1 Inability to Prove with this Pumping Lemma 4.9 Regularity-Preserving Transformations Aid Proofs 5: Designing DFA 5.1 Understanding the Language to Be Realized 5.1.1 The Language of Equal Changes 5.1.2 Best Practices to Correct DFA Design and Verification 5.2 Examples of Designing DFA 5.2.1 The Language of Blocks of 3 5.2.2 DFA for “Ends with 0101” 5.2.3 DFA for “MSB/LSB-first Binary Number is Divisible by 3” 5.2.4 DFA for “Third-last bit is a 1” 5.3 Automd: A Markdown Language for All Machines 5.3.1 Markdown for DFA 6: Operations on DFA 6.1 Complementation of DFA 6.2 Union and Intersection of DFA 6.3 Language Equivalence and Isomorphism 6.4 DFA Minimization and Myhill-Nerode Theorem 6.4.1 Fully Worked-out Example of DFA Minimization 6.4.2 Salient Code Excerpts 6.5 Examples of Language Design and Manipulation 6.5.1 Use of Union, Minimization, and Language Equivalence 6.5.2 Use of DeMorgan’s Law 7: Nondeterministic Finite Automata 7.1 Overview of NFA 7.2 Formal Description of NFA 7.3 Language of an NFA: Example Driven 7.3.1 Simulations of the NFA of Figure 7.5 7.3.2 Simulations of the NFA of Figure 7.3 7.4 Language of an NFA: via Eclosure 7.4.1 Defining Eclosure 7.4.2 Definition of d and d^ 7.5 NFA to DFA Conversion through Subset Construction 7.6 Brzozowski’s DFA Minimization Algorithm 7.6.1 Reversal of a DFA Yields an NFA 7.7 A Complete Illustration of Brzozowski’s Minimization 8: Regular Expressions and NFA 8.1 Regular Expressions 8.2 RE to NFA Conversion: Examples, Algorithm Sketch 8.3 A More Extensive Example 8.4 Regular Expressions: Ubiquitous, yet Error-Prone 8.5 Anatomy of the RE to NFA Converter 8.6 Example: Designing an Error-Correcting DFA 8.6.1 Error-correcting RE for “within Hamming Distance of 2” 8.6.2 NFA-based Design of “within Hamming Distance of 2” 8.7 Minimal DFA and Isomorphism 8.8 DFA Ultimate Periodicity to Solve the Postage Stamp Problem 8.8.1 Ultimately periodic sets and lengths of members of a regular language 8.8.2 Stamp Problem and Ultimate Periodicity via Jove 8.8.3 Applying to numbers that are not relatively prime 8.8.4 Solving for three stamps 8.8.5 Lengths of strings accepted by DFA 9: NFA to RE Conversion 9.1 NFA to RE Conversion Algorithm 9.2 Illustration on Pedagogical Example 9.3 Illustration on Non-trivial Example 9.4 Checking the Conversion 9.5 DFA, NFA, and RE Are Equally Powerful 9.6 Implementation of NFA to RE 9.7 Closure Results Pertaining to Regular Languages 10: Derivative-Based Regular Expression Matching 10.1 Introduction to RE Derivatives 10.2 Definitions 10.2.1 Derivative Rules 10.2.2 Nullability Rules 10.3 Implementation of Derivative-Based String Matching 10.3.1 Derivatives: Closing Thoughts 11: Context-Free Languages and Grammars 11.1 Context-Free Language Examples 11.2 Context-Free Grammars and Parse Trees 11.2.1 Elements of Context-Free Grammars 11.2.2 Parse Trees, Language of a CFG 11.3 Avoiding Mistakes in Designing CFGs 11.3.1 Completeness and Consistency 11.4 The Design of CFG, and the Hill/Valley Plot for Arguing Consistency and Completeness 11.5 Ambiguous Grammars, and Disambiguation 11.5.1 Disambiguation 11.5.2 Disambiguation Is Crucial! 11.5.3 Impossibility Results 11.6 Inherently Ambiguous Languages 11.7 Expressing DFA via CFGs 11.7.1 Purely Right Linear Grammars 11.7.2 Closure, Purely Left Linear, and Mixed Linearity 11.8 Historical Importance of the Theory of Parsing 11.8.1 Combating Inherent Ambiguity 11.9 A Pumping Lemma for CFLs 11.9.1 Application of the CFL Pumping Lemma 11.10 The Complement of a Non-CFL Can Be a CFL 11.10.1 Growing “Inside-Out” 12: Pushdown Automata 12.1 Pushdown Automaton Basics 12.2 Formal Description of PDA 12.2.1 Acceptance, Deterministic PDA 12.3 Exploring the PDA for LDyck Using Jove 12.4 PDA Behavior Through Examples 12.4.1 Rerunning pda6 with Larger Stack Allowed 12.5 Toward More Practical PDA 12.6 CFG to PDA Conversion 12.6.1 Disambiguation 12.7 Practical Knowledge Imparted by Jove: Three Parsers 13: Turing Machines 13.1 Brief History of Turing Machines 13.2 Universal Computing Devices 13.3 Formal Definition of Turing Machines 13.4 Examples of Simple TMs 13.4.1 A Simple DTM that Flips Bits 13.4.2 TMs that check if a string contains 101 13.5 A DTM for w w and an NDTM for ww 13.5.1 A DTM Recognizing w w 13.5.2 A Nondeterministic TM Recognizing ww 13.5.3 Nondeterminism does not increase a TM’s Expressive Power 13.6 Example: A TM that Works on the Collatz Problem 13.6.1 Markdown for the Collatz Problem TM with Comments 13.7 The Chomsky Hierarchy 13.7.1 Recursively Enumerable and Recursive Languages 13.8 An Alternate Notation for Instantaneous Descriptions 14: Interplay between Formal Languages 14.1 Why Study Impossibility Results? 14.1.1 Definitions: Procedure and Algorithm 14.1.2 Formal Languages Associated with Turing Machines 14.1.3 Allaying Confusion: Language vs. Language Family 14.2 One Example of a Recursive and an RE Language 14.2.1 A Recursive Language 14.2.2 Prerequisites to Defining the Notion of RE 14.2.3 Combining Semi-deciders for L and L 14.2.4 The “no wimp” Clause 14.2.5 A Recursively Enumerable Language 14.3 Other Examples of Recursive and RE Languages 14.3.1 RE Languages that are not Recursive 14.3.2 Why is it called Recursively Enumerable? 14.3.3 Alternate proof of ATM being RE 14.3.4 Some More RE Languages 14.4 Summary of Decidability/Semi-Decidability Results 14.4.1 Existence of Non-RE languages 14.5 RE and Recursive Sets: More High-Level Proof Sketches 14.5.1 Language of DFA D where L(D) Æ §¤ is Recursive 14.5.2 Language of CFG G where L(G) Æ; is Recursive 14.5.3 Language of LBA that halt on input w is Recursive 14.5.4 Language of Turing machines whose first output is ‘3’ 15: Post Correspondence, and Other Undecidability Proofs 15.1 Post Correspondence: “Drosophila” for Decidability 15.2 Proof Sketch of the Undecidability of PCP 15.2.1 Tile Construction Basics 15.2.2 Proving Grammar Ambiguity by Reduction from PCP 15.2.3 PCP in Jove 15.3 Undecidability of the Acceptance Problem 15.4 Halting (HaltTM) is Undecidable 15.5 Mapping Reductions 15.5.1 Undecidable problems are “ATM in disguise” 16: NP-Completeness 16.1 What Does NP-Complete Mean? 16.1.1 Grouping Problems: Solving One Implies Solving All 16.1.2 Some Historical Notes 16.2 NPC Notions Defined Based on NDTMs 16.2.1 P-time 16.2.2 NP-time 16.2.3 NP Verifier 16.2.4 Examples of P-time and NP-time Deciders 16.2.5 Decider versus Verifier Views 16.3 Introducing SAT Problems 16.3.1 A Warmup: 2-SAT 16.3.2 2-SAT: Examples and Algorithm 16.4 3-SAT and Its NP-Completeness 16.5 3-SAT Is NP-Complete 16.5.1 3-SAT is in NP 16.5.2 Every Language in NP Reduces to 3-SAT 16.5.3 How P=NP is Obtained if 3-SAT 2 P? 16.6 Show that Clique Is NPC: Reduction from 3-SAT 16.6.1 Clique is in NP 16.6.2 Some Language in NPC Reduces to Clique 16.7 Complexity Classes, Closing Caveats 16.7.1 NP-Hard Problems can be Undecidable (Pitfall in Proofs) 16.7.2 The CoNP and CoNPC Complexity Classes 16.8 SAT in Practice 17: Binary Decision Diagrams as Minimal DFA 17.1 Boolean Functions in Computing Theory and Practice 17.2 Boolean Functions as Minimal DFA of Their On-Sets 17.3 The Importance of Variable Ordering 17.3.1 Finding a better input variable order 17.3.2 Functions with linearly sized BDDs 17.4 From Minimal DFA to BDD: Intuitive Presentation 17.5 On BDD Sizes 18: Computability Using Lambdas 18.1 The History of Lambda Calculus 18.2 Lambdas from a Programmer’s Perspective 18.3 Syntax and Semantics of the Lambda Calculus 18.4 Illustration: Church Numerals in Python 18.5 Illustration: Booleans, Pairs, Other Functions 18.6 Handling Recursion 18.7 Obtaining Fixpoints from Fixpoint Equations 18.7.1 Y: A Fixpoint Finder 18.7.2 The Y Combinator 18.7.3 Expression Recursion using Y 18.7.4 Reason for an alternate fixpoint finder Ye 18.8 Illustrating the Use of Fixpoint Combinators 18.9 Combinators Appendices Appendix A: A Recap of Discrete Math A.1 Sets A.1.1 Set Builder A.1.2 Powerset A.1.3 Complement A.1.4 Equivalence Classes, Partitioning A.2 Mathematical Logic A.3 Proof Methods: Using Contrapositive, by Contradiction A.4 Cartesian Product, Binary Relations, Functions A.5 Functions: Signature, Onto, Into, Total A.6 Trees Appendix B: Catalog of Jove Functions B.1 Jove’s Top-Level Functions B.1.1 Chapters 2 and 3 B.1.2 Chapters 4 through 6 B.1.3 Chapters 7 through 9 B.1.4 Chapter 10 B.1.5 Chapter 11 B.1.6 Chapter 12 B.1.7 Chapter 13 B.1.8 Chapter 15 B.1.9 Chapters 16 and 17 B.1.10 Chapter 18 B.2 Jove’s Use of Python, Including Lambda Basics Appendix C: There Are More Languages than RE Languages C.1 Gödel Hash C.2 Cantor-Schröder-Bernstein (CSB) Theorem C.3 Cantor’s Diagonalization Proof about Languages C.4 l Real l Is Higher than l Nat l Selected References Index
Donate to keep this site alive
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.