Automata Theory and Formal Languages

Содержание книги "Automata Theory and Formal Languages : a practical handbook"

Foreword
Introduction
1. Symbols, Strings and Languages
1.1. Alphabet, Strings, Operations over Strings
1.2. Languages, Operation over Languages
1.3. Solved Examples
1.4. Class Exercises
1.5. Exercises for Self-Study
1.6. Self-Assessment Questions
2. Formal Grammars
2.1. Definition of Formal Grammar
2.2. Classification of Grammars (Chomsky Hierarchy)
2.3. Note on the Relationship Between Grammar and Language
2.4. Solved Examples
2.5. Class Exercises
2.6. Exercises for Self-Study
2.7. Self-Assessment Questions
3. Regular Expressions
3.1. Introduction to Regular Expressions
3.2. Regular Sets and Regular Languages
3.3. Properties of Regular Expressions
3.4. Order of Operations in Regular Expressions
3.5. Regular Expression Equations
3.6. System of Equations with Regular Coefficients
3.7. Regular and Right-Linear Languages
3.8. Solved Examples
3.9. Class Exercises
3.10. Exercises for Self-Study
3.11. Self-Assessment Questions
4. Finite Automata
4.1. Main Definitions
4.2. Graph of a Finite Automaton
4.3. Extending Incomplete DFA to Completely Specified DFA
4.4. Equivalence of NFA and DFA
4.5. Finite Automaton with ε-Transitions (ε-NFA)
4.6. Equivalence of ε-NFA and DFA
4.7. Comparison ε-NFA, NFA and DFA
4.8. Minimization of Finite Automata
4.9. Solved Examples
4.10. Class Exercises
4.11. Exercises for Self-Study
4.12. Self-Assessment Questions
5. Equivalence of Finite-Automaton, Regular, and Right-Linear Languages
5.1. Kleene’s Theorem
5.2. Connection between Right-Linear and Regular Languages
5.3. Connection between Regular Expressions and Finite Automata
5.4. Connection between RL Grammars and Finite Automata
5.5. The Pumping Lemma for Regular Languages
5.6. Solved Examples
5.8. Exercises for Self-Study
5.9. Self-Assessment Questions
6. Pushdown Automaton
6.1. The Chomsky Hierarchy: Grammars, Languages, and Automata
6.2. Pushdown Automaton: An Informal Overview
6.3. Pushdown Automaton: Formal Definition
6.4. Graph of a Pushdown Automaton
6.5. Solved Examples
6.6. Class Exercises
6.7. Exercises for Self-Study
6.8. Self-Assessment Questions
Appendices
Appendix A. Course Projects: Building Automata Theory Tools
Appendix B. Backus-Naur Form
Appendix C. Modeling Character Behavior in Computer Games
Appendix D. Index of Algorithms
Appendix E. Index of Theorems and Lemmas
Appendix F. Sample Assignments for Written Work
References