Automata and Computability A Programmer Perspective Ganesh Gopalakrishnan 1351374281 9781351374286
Original price was: $50.00.$25.00Current price is: $25.00.
Automata and Computability A Programmer Perspective Ganesh Gopalakrishnan – Ebook Instant Download/Delivery ISBN(s): 1351374281, 9781351374286
Product details:
- ISBN 10: 1351374281
- ISBN 13: 9781351374286
- Author: Ganesh
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.
Table of contents:
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 δ and δ^
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 ∈ 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
People also search:
automata and computability by dexter c. kozen pdf
automata computability and complexity theory and applications
automata computability and complexity
automata theory and computability
automata theory and computability vtu notes
You may also like…
Computers - Programming
Becoming A Programmer A Beginner s Guide 1st Edition Paul Mabry
Mathematics - Computational Mathematics
Computers - Programming