دانلود کتاب Automata Theory and Formal Languages: Fundamental Notions, Theorems, and Techniques (Undergraduate Topics in Computer Science)

فهرست مطالب :

Preface
Contents
CHAPTER 1 Formal Grammars and Languages
1.1. Free Monoids
1.2. Formal Grammars
1.3. The Chomsky Hierarchy
1.4. Chomsky Normal Form and Greibach Normal Form
1.5. Epsilon Productions
1.6. Derivations in Context-Free Grammars
1.7. Substitutions and Homomorphisms
CHAPTER 2 Finite Automata and Regular Grammars
2.1. Deterministic and Nondeterministic Finite Automata
2.2. Nondeterministic Finite Automata and S-extendedType 3 Grammars
2.3. Finite Automata and Transition Graphs
2.4. Left Linear and Right Linear Regular Grammars
2.5. Finite Automata and Regular Expressions
2.6. Arden Rule
2.7. Axiomatization of Equations Between Regular Expressions
2.8. Minimization of Finite Automata
2.9. Pumping Lemma for Regular Languages
2.10. A Parser for Regular Languages
2.10.1. A Java Program for Parsing Regular Languages.
2.11. Generalizations of Finite Automata
2.11.1. Moore Machines.
2.11.2. Mealy Machines.
2.11.3. Generalized Sequential Machines.
2.12. Closure Properties of Regular Languages
2.13. Decidability Properties of Regular Languages
CHAPTER 3 Pushdown Automata and Context-Free Grammars
3.1. Pushdown Automata and Context-Free Languages
3.2. From PDA’s to Context-Free Grammars and Back: Some Examples
3.3. Deterministic PDA’s and Deterministic Context-Free Languages
3.4. Deterministic PDA’s and Grammars in Greibach Normal Form
3.5. Simplifications of Context-Free Grammars
3.5.1. Elimination of Nonterminal Symbols That Do Not Generate Words.
3.5.2. Elimination of Symbols Unreachable from the Start Symbol.
3.5.3. Elimination of Epsilon Productions.
3.5.4. Elimination of Unit Productions.
3.5.5. Elimination of Left Recursion.
3.6. Construction of the Chomsky Normal Form
3.7. Construction of the Greibach Normal Form
3.8. Theory of Language Equations
3.9. Summary on the Transformations of Context-Free Grammars
3.10. Self-Embedding Property of Context-Free Grammars
3.11. Pumping Lemma for Context-Free Languages
3.12. Ambiguity and Inherent Ambiguity
3.13. Closure Properties of Context-Free Languages
3.14. Basic Decidable Properties of Context-Free Languages
3.15. Parsers for Context-Free Languages
3.15.1. The Cocke-Younger-Kasami Parser.
3.15.2. The Earley Parser.
3.16. Parsing Classes of Deterministic Context-Free Languages
3.17. Closure Properties of Deterministic Context-Free Languages
3.18. Decidable Properties of Deterministic Context-Free Languages
CHAPTER 4 Linear Bounded Automata and Context-Sensitive Grammars
4.1. Recursiveness of Context-Sensitive Languages
CHAPTER 5 Turing Machines and Type 0 Grammars
5.1. Turing Machines
5.2. Equivalence Between Turing Machines and Type 0 Languages
CHAPTER 6 Decidability and Undecidability in Context-Free Languages
6.1. Preliminary Definitions and Theorems
6.2. Basic Decidability and Undecidability Results
6.2.1. Basic Undecidable Properties of Context-Free Languages.
6.3. Decidability in Deterministic Context-Free Languages
6.4. Undecidability in Deterministic Context-Free Languages
6.5. Undecidable Properties of Linear Context-Free Languages
CHAPTER 7 Supplementary Topics
7.1. Iterated Counter Machines and Counter Machines
7.2. Stack Automata
7.3. Relationships Among Various Classes of Automata
7.4. Decidable Properties of Classes of Languages
7.5. Algebraic and Closure Properties of Classes of Languages
7.6. Abstract Families of Languages
7.7. Finite Automata to/from S-extended Regular Grammars
7.8. Context-Free Grammars over Singleton Terminal Alphabets
7.9. The Bernstein Theorem
7.10. Existence of Functions That Are Not Computable
List of Algorithms and Programs
Index
Bibliography