Knowledge of automata theory and formal languages is crucial for understanding human-computer interaction, as well as for understanding the various processes that take place when manipulating knowledge if that knowledge is, indeed, expressed as sentences written in a suitably formalized language. In particular, it is at the basis of the theory of parsing, which plays an important role in language translation, compiler construction, and knowledge manipulation in general.Presenting basic notions and fundamental results, this concise textbook is structured on the basis of a correspondence that exists between classes of automata and classes of languages. That correspondence is established by the fact that the recognition and the manipulation of sentences in a given class of languages can be done by an automaton in the corresponding class of automata. Four central chapters center on: finite automata and regular languages; pushdown automata and context-free languages; linear bounded automata and context-sensitive languages; and Turing machines and type 0 languages. The book also examines decidable and undecidable problems with emphasis on the case for context-free languages.
Topics and features:
- Provides theorems, examples, and exercises to clarify automata-languages correspondences
- Presents some fundamental techniques for parsing both regular and context-free languages
- Classifies subclasses of decidable problems, avoiding focus on the theory of complexity
- Examines finite-automata minimalization and characterization of their behavior using regular expressions
- Illustrates how to derive grammars of context-free languages in Chomsky and Greibach normal forms
- Offers supplementary material on counter machines, stack automata, and abstract language families
This highly useful, varied text/reference is suitable for undergraduate and graduate courses on automata theory and formal languages, and assumes no prior exposure to these topics nor any training in mathematics or logic.
Alberto Pettorossi is professor of theoretical computer science at the University of Rome Tor Vergata, Rome, Italy.
Author(s): Alberto Pettorossi
Series: Undergraduate Topics in Computer Science
Publisher: Springer
Year: 2022
Language: English
Pages: 286
City: Cham
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
