Introduction to Formal Languages

Preface Chapter 1. The Notion of Formal Language 1.1 Basic Concepts and Notations 1.2 The Chomsky Hierarchy of Languages Chapter 2. Operations on Languages 2.1 Definitions of Operations on Languages 2.2 Closure Properties of Language Classes Chapter 3. Context-Free Languages 3.1 The Chomsky Normal Form 3.2 Derivation Tree 3.3 Linear Grammars and Regular Languages 3.4 Griebach Normal Form 3.5 Regular Expressions Chapter 4. Context-Sensitive Languages 4.1 Length-Increasing Grammars 4.2 Kuroda Normal Form 4.3 One-Sided Context-Sensitive Grammars Chapter 5. Unrestricted Phrase-Structure Languages 5.1 A Normal Form for Type O Grammars 5.2 Derivation Graph Chapter 6. Automata and Their Languages 6.1 Finite Automata 6.2 Pushdown Automata 6.3 Two-Pushdown Automata 6.4 Turing Machines Chapter 7. Decidability 7.1 Recursive and Recursively Enumerable Languages 7.2 The Church-Turing Thesis 7.3 Undecidable Problems Chapter 8. Complexity of Computations 8.1 Deterministic and Nondeterministic Procedures 8.2 Measures of Complexity 8.3 Complexity of Context-Free Language Recognition 8.4 The Hardest Context-Free Language Chapter 9. Syntax Analysis 9.1 The Connection between Syntax and Semantics 9.2 Ambiguity 9.3 Earley's Algorithm 9.4 LL(k) and LR(k) Grammars Chapter 10. Derivation Languages 10.1 Operations on Derivations 10.2 Derivation Words 10.3 Algebraic Properties of the Fundamental Operations 10.4 Canonical Derivations and Graph Traversals 10.5 The Context-Sensitivity of Derivation Languages 10.6 Derivations in Context-Sensitive Grammars Appendix. Elements of Set Theory Bibliographic Notes; References; Index