Introduction to automata theory, languages, and computation

"Introduction to automata theory, languages, and computation" Table Of Contents:

• 1- Automata: The Methods and the Madness
• 2- Why Study Automata Theory
• 3- Introduction to Finite Automata
• 4- Structural Representations
• 5- Automata and Complexity
• 6- Introduction to Formal Proof
• 7- Deductive Proofs
• 8- Reduction to Definitions
• 9- Other Theorem Forms
• 10- Theorems That Appear Not to Be If-Then Statements
• 11- Additional Forms of Proof
• 12- Proving Equivalences About Sets
• 13- The Contrapositive
• 14- Proof by Contradiction
• 15- Counterexamples
• 16- Inductive Proofs
• 17- Induction on Integers
• 18- More General Forms of Integer Inductions
• 19- Structural Inductions
• 20- Mutual Inductions
• 21- The Central Concepts of Automata Theory
• 22- Alphabets
• 23- Strings
• 24- Languages
• 25- Problems
• 26- Summary of Chapter 1
• 27- Gradiance Problems for Chapter 1
• 28- References for Chapter 1
• 29- Finite Automata
• 30- An Informal Picture of Finite Automata
• 31- The Ground Rules
• 32- The Protocol
• 33- Enabling the Automata to Ignore Actions
• 34- The Entire System as an Automaton
• 35- Using the Product Automaton to Validate the Protocol
• 36- Deterministic Finite Automata
• 37- Definition of a Deterministic Finite Automoton
• 38- How a DFA Processes Strings
• 39- Simpler Notations for DFA's
• 40- Extending the Transition Function to Strings
• 41- The Language of a DFA
• 42- Exercises for Section 2.2
• 43- Nondeterministic Finite Automata
• 44- An Informal View of Nondeterministic Finite Automata
• 45- Definition of Nondeterministic Finite Automata
• 46- The Extended Transition Function
• 47- The Language of an NFA
• 48- Equivalence of Deterministic and Nondeterministic Finite Automata
• 49- A Bad Case for the Subset Construction
• 50- Exercises for Section 2.3
• 51- An Application: Text Search
• 52- Finding Strings in Text
• 53- Nondeterministic Finite Automata for Text Search
• 54- A DFA to Recognize a Set of Keywords
• 55- Exercises for Section 2.4
• 56- Finite Automata With EpsilonTransitions
• 57- Uses of ϵ-Transitions
• 58- The Formal Notation for an ϵ-NFA
• 59- Epsilon-Closures
• 60- Extended Transitions and Languages for ϵ-NFA's
• 61- Eliminationg ϵ-Transitions
• 62- Exercises for Section 2.5
• 63- Summary of Chapter 2
• 64- Gradiance Problems for Chapter 2
• 65- References for Chapter 2
• 66- Regular Expressions and Languages
• 67- Regular Expressions
• 68- The Operators of Regular Expressions
• 69- Bulding Regular Expressions
• 70- Precedence of Regular-Expression Operators
• 71- Exercises for Section 3.1
• 72- Finite Automata and Regular Expressions
• 73- From DFA's to Regular Expressions
• 74- Converting DFA's to Regular Expressions by Eliminating States
• 75- Converting Regular Expressions to Automata
• 76- Exercises for Section 3.2
• 77- Applications of Regular Expressions
• 78- Regular Expressions in UNIX
• 79- Lexical Analysis
• 80- Finding Patterns in Text
• 81- Exercises for Section 3.3
• 82- Algebraic Laws for Regular Expressions
• 83- Associativity and Commutativity
• 84- Identities and Annihilators
• 85- Distributive Laws
• 86- The Idempotent Laws
• 87- Laws Involving Closures
• 88- Discovering Laws for Regular Expressions
• 89- The Test for a Regular-Expression Algebraic Law
• 90- Exercises for Section 3.4
• 91- Summary of Chapter 3
• 92- Gradiance Problems for Chapter 3
• 93- References for Chapter 3
• 94- Properties of Regular Languages
• 95- Proving Languages Not to Be Regular
• 96- The Pumping Lemma for Regular Languages
• 97- Applications of the Pumping Lemma
• 98- Exercises for Section 4.1
• 99- Closure Properties of Regular Languages
• 100- Closure of Regular Languages Under Boolean Operations
• 101- Reversal
• 102- Homomorphisms
• 103- Inverse Homomorphisms
• 104- Exercises for Section 4.2
• 105- Decision Properties of Regular Languages
• 106- Converting Among Representations
• 107- Testing Emptiness of Regular Languages
• 108- Testing Membership in a Regular Language
• 109- Exercises for Section 4.3
• 110- Equivalence and Minimization of Automata
• 111- Testing Equivalence of States
• 112- Testing Equivalence of Regular Languages
• 113- Minimization of DFA's
• 114- Why the Minimized DFA Can't Be Beaten
• 115- Exercises for Section 4.4
• 116- Summary of Chapter 4
• 117- Gradiance Problems for Chapter 4
• 118- References for Chapter 4
• 119- Context-Free Grammars and Languages
• 120- Context-Free Grammars
• 121- An Informal Example
• 122- Definition of Context-Free Grammars
• 123- Derivations Using a Grammar
• 124- Leftmost and Rightmost Derivations
• 125- The Language of a Grammar
• 126- Sentential Forms
• 127- Exercises for Section 5.1
• 128- Parse Trees
• 129- Constructing Parse Trees
• 130- The Yield of a Parse Tree
• 131- Inference, Derivations, and Parse Trees
• 132- From Inferences to Trees
• 133- From Trees to Derivations
• 134- From Derivations to Recursive Inferences
• 135- Exercises for sectino 5.2
• 136- Applications of Context-Free Grammars
• 137- Parsers
• 138- The YACC Parser-Generator
• 139- Markup Languages
• 140- XML and Document-Type Definitions
• 141- Exercises for Section 5.3
• 142- Ambiguity in Grammars and Languages
• 143- Ambiguous Grammars
• 144- Removing Ambiguity From Grammars
• 145- Leftmost Derivations as a Way to Express Ambiguity
• 146- Inherent Ambiguity
• 147- Exercises for Section 5.4
• 148- Summary of Chapter 5
• 149- Gradiance Problems for Chapter 5
• 150- References for Chapter 5
• 151- Pushdown Automata
• 152- Definition of the Pushdown Automaton
• 153- Informal Introduction
• 154- The Formal Definition of Pushdown Automata
• 155- A Graphical Notation for PDA's
• 156- Instantaneous Descriptions of a PDA
• 157- Exercises for Section 6.1
• 158- The Languages of a PDA
• 159- Acceptance by Final State
• 160- Acceptance by Empty Stack
• 161- From Empty Stack to Final State
• 162- From Final State to Empty Stack
• 163- Exercises for Section 6.2
• 164- Equivalence of PDA's and CFG's
• 165- From Grammars to Pushdown Automata
• 166- From PDA's to Grammars
• 167- Exercises for Section 6.3
• 168- Deterministic Pushdown Automata
• 169- Definition of a Deterministic PDA
• 170- Regular Languages and Deterministic PDA's
• 171- DPDA's and Context-Free Languages
• 172- DPDA's and Ambiguous Grammars
• 173- Exercises for Section 6.4
• 174- Summary of Chapter 6
• 175- Gradiance Problems for Chapter 6
• 176- References for Chapter 6
• 177- Properties of Context-Free Languages
• 178- Normal Forms for Context-Free Grammars
• 179- Eliminating Useless Symbols
• 180- Computing the Generating and Reachable Symbols
• 181- Eliminating ϵ-Productions
• 182- Eliminating Unit Productions
• 183- Chomsky Normal Form
• 184- Exercises For Section 7.1
• 185- The Pumping Lemma for Context-Free Languages
• 186- The Size of Parse Trees
• 187- Statement of the Pumping Lemma
• 188- Applications of the Pumping Lemma for CFL's
• 189- Exercises for Section 7.2
• 190- Closure Properties of Context-Free Languages
• 191- Substitutions
• 192- Applications of the Substitution Theorem
• 193- Reversal
• 194- Intersection With a Regular language
• 195- Inverse Homomorphism
• 196- Exercises for Section 7.3
• 197- Decision Properties of CFL's
• 198- Complexity of Converting Among CFG's and PDA's
• 199- Running Time of Conversion to Chomsky Normal Form
• 200- Testing Emptiness of CFL's
• 201- Testing Membership in a CFL
• 202- Preview of Undecidable CFL Problems
• 203- Exercises for Section 7.4
• 204- Summary of Chapter 7
• 205- Gradiance Problems for Chapter 7
• 206- References for Chapter 7
• 207- Introduction to Turing Machines
• 208- Problems That Computers Cannot Solve
• 209- Programs that Print "Hello, World"
• 210- The Hypothetical "Hello, World" Tester
• 211- Reducing One Problem to Another
• 212- Exercises for Section 8.1
• 213- The Turing Machine
• 214- The Quest to Decide All Mathematical Questions
• 215- Notation for the Turing Machine
• 216- Instantaneous Descriptions for Turing Machines
• 217- Transition Diagrams for Turing Machines
• 218- The Language of a Turing Machine
• 219- Turing Machines and Halting
• 220- Exercises for Section 8.2
• 221- Programming Techniques for Turing Machines
• 222- Storage in the State
• 223- Multiple Tracks
• 224- Subroutines
• 225- Exercises for Section 8.3
• 226- Extensions to the Basic Turing Machine
• 227- Multitape Turing Machines
• 228- Equivalence of One-Tape and Multitape TM's
• 229- Running Time and the Many-Tapes-to-One Construction
• 230- Nondeterministic Turing Machines
• 231- Exercises for Section 8.4
• 232- Restricted Turing Machines
• 233- Turing Machines with Semi-infinite Tapes
• 234- Multistack Machines
• 235- Counter Machines
• 236- The Power of Counter Machines
• 237- Exercises for Section 8.5
• 238- Turing Machines and Computers
• 239- Simulating a Turing Machine by Computer
• 240- Simulating a Computer by a Turing Machine
• 241- Comparing the Running Times of Computers and Turing Machines
• 242- Summary of Chapter 8
• 243- Gradiance Problems for Chapter 8
• 244- References for Chapter 8
• 245- Undecidability
• 246- A Language That Is Not Recursively Enumerable
• 247- Enumerating the Binary Strings
• 248- Codes for Turing Machines
• 249- The Diagonalization Language
• 250- Proof that L[d]XXX Is Not Recursively Enumerable
• 251- Exercises for Section 9.1
• 252- An Undecidable Problem That Is RE
• 253- Recursive Languages
• 254- Complements of Recursive and RE languages
• 255- The Universal Language
• 256- Undecidability of the Universal Language
• 257- Exercises for Section 9.2
• 258- Undecidable Problems About Turing Machines
• 259- Reductions
• 260- Turing Machines That Accept the Empty Language
• 261- Rice's Theorem and Properties of the RE Languages
• 262- Problems and Turing-Machine Specifications
• 263- Exercises for Section 9.3
• 264- Post's Correspondence Problem
• 265- Definition of Post's Correspondence Problem
• 266- The "Modified" PCP
• 267- Completion of the Proof of PCP Undecidability
• 268- Exercises for Section 9.4
• 269- Other Undecidable Problems
• 270- Problems About Programs
• 271- Undecidability of Ambiguity for CFG's
• 272- The Complement of a List Language
• 273- Exercises for Section 9.5
• 274- Summary of Chapter 9
• 275- Gradiance Problems for Chapter 9
• 276- References for Chapter 9
• 277- Intractable Problems
• 278- The Classes P and NP
• 279- Problems Solvable in Polynomial Time
• 280- An Example: Kruskal's Algorithm
• 281- Nondeterministic Polynomial Time
• 282- An NP EXample: The Traveling Salesman Problem
• 283- Polynomial-Time Reductions
• 284- NP-Complete Problems
• 285- Exercises for Section 10.1
• 286- An NP-Complete Problem
• 287- The Satisfiability Problem
• 288- Representing SAT Instances
• 289- NP-Completeness of the SAT Problem
• 290- Exercises for Section 10.2
• 291- A Restricted Satisfiability Problem
• 292- Normal forms for Boolean Expressions
• 293- Converting Expressions to CNF
• 294- NP-Completeness of CSAT
• 295- NP-Completeness of 3SAT
• 296- Exercises for Section 10.3
• 297- Additional NP-Complete Problems
• 298- Describing NP-complete Problems
• 299- The Problem of Independent Sets
• 300- The Node-Cover Problem
• 301- The Directed Hamilton-Circuit Problem
• 302- Undirected Hamilton Circuits and the TSP
• 303- Summary of NP-Complete Problems
• 304- Exercises for Section 10.4
• 305- Summary of Chapter 10
• 306- Gradiance Problems for Chapter 10
• 307- References for Chapter 10
• 308- Additional Classes of Problems
• 309- Complements of Languages in NP
• 310- The Class of Languages Co-NP
• 311- NP-Complete Preblems and Co-NP
• 312- Exercises for Section 11.1
• 313- Problems Solvable in Polynomial Space
• 314- Polynomial-Space Turing Machines
• 315- Relationship of PS and NPS to Previously Defined Classes
• 316- Deterministic and Nondeterministic Polynomial Space
• 317- A Problem That Is Complete for PS
• 318- PS-Completeness
• 319- Quantified Boolean Formulas
• 320- Evaluating Quantified Boolean Formulas
• 321- PS-Completeness of the QBF Problem
• 322- Exercises for Section 11.3
• 323- Language Classes Based on Randomization
• 324- Quicksort: an Example of a Randomized Algorithm
• 325- A Turing-Machine Model using Randomization
• 326- The Language of a Randomized Turing Machine
• 327- The Class RP
• 328- Recognizing Languages in RP
• 329- The Class ZPP
• 330- Relationship Between RP and ZPP
• 331- Relationships to the Classes P and NP
• 332- The Complexity of Primality Testing
• 333- The Importance of Testing Primality
• 334- Introduction to Modular Arithmetic
• 335- The Complexity of Modular-Arithmetic Computations
• 336- Random-Polynomial Primality Testing
• 337- Nondeterministic Primality Tests
• 338- Exercises for Section 11.5
• 339- Summary of Chapter 11
• 340- Gradiance Problems for Chapter 11
• 341- References for Chapter 11
• 342- Index

"Introduction to automata theory, languages, and computation" Description:

Read “Introduction to automata theory, languages, and computation”:

Read “Introduction to automata theory, languages, and computation” by choosing from the options below.