Introduction to Formal Languages

by György E. Révész

Overview

This carefully written introductory treatment covers all areas of mainstream formal language theory, including operations on languages, context-sensitive languages, automata, decidability, and syntax analysis, as well as the first complete discussion of derivation languages. It features numerous worked examples, problem exercises, and elegant mathematical proofs for almost all theorems. 1983 edition.

Product Details

ISBN-13:	9780486666976
Publisher:	Dover Publications
Publication date:	03/16/2012
Series:	Dover Books on Mathematics
Pages:	208
Product dimensions:	5.38(w) x 8.50(h) x (d)

About the Author

Gyorgy Revesz is Professor Emeritus in the Department of Computer Science at the University of North Carolina at Charlotte.

Table of Contents

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