Formal languages and computation: models and their applications/ Alexander Meduna

Includes bibliographical references and index.

SECTION I INTRODUCTION
1 Mathematical Background
1.1 Logic..
1.2 Sets and Sequences.».
1.3 Relations.
1.4 Graphs...^
2 Formal Languages and Rewriting Systems..
2.1 Formal Languages...
2.2 Rewriting Systems...
2.2.1 Rewriting Systems in General..
2.2.2 Rewriting Systems as Language Models ..
2.2.3 Rewriting Systems as Computational Models..
2.3 Synopsis of the Book
SECTION II REGULAR LANGUAGES AND THEIR MODELS
3 Models for Regular Languages..
3.1 Finite Automata..
3.1.1 Representations of Finite Automata..
3.2 Restricted Finite Automata
3.2.1 Removal of e-Rules...
3.2.2 Determinism.
3.2.2.1 Complete Specification....
3.2.3 Minimization...
3.3 Regular Expressions and Their Equivalence with Finite Automata
3.3.1 Regular Expressions..
3.3.2 Equivalence with Finite Automata..
3.3.2.1 From Finite Automata to Regular Expressions..
3.3.2.2 From Regular Expressions to Finite Automata..
4 Applications of Regular Expressions and Finite Automata:
Lexical Analysis.
4.1 Implementation of Finite Automata.
4.1.1 Table-Based Implementation
4.1.2 Case-Statement Implementation
4.2 Introduction to Lexical Analysis
4.2.1 Lexical Units and Regular Expressions.
4.2.2 Scanners and Finite Automata.
4.3 Implementation of a Scanner.
5 Properties of Regular Languages.
5.1 Pumping Lemma for Regular Languages .,
5.1.1 Applications of the Pumping Lemma for Regular Languages..
5.2 Closure Properties
5.2.1 Applications of Closure Properties..
SECTION 111 CONTEXT-FREE LANGUAGES AND THEIR MODELS
6 Models for Contact-Free Languages.
6.1 Context-Free Grammars
6.2 Restricted Context-Free Grammars.
6.2.1 Canonical Derivations and Derivation Trees.
6.2.1.1 Leftmost Derivations.
6.2.1.2 Rightmost Derivations..
6.2.1.3 Derivation Trees
6.2.1.4 Ambiguity.
6.2.2 Removal of Useless Symbols
6.2.3 Removal of Erasing Rules.
6.2.4 Removal of Single Rules.
6.2.5 Chomsky Normal Form.
6.2.6 Elimination of Left Recursion
6.2.7 Greibach Normal Form
6.3 Pushdown Automata
6.3.1 Pushdown Automata and Iheir Languages...
6.3.2 Equivalence with Context-Free Grammars...
6.3.2.1 From Context-Free Grammars to
Pushdown Automata
6.3.2.2 From Pushdown Automata to Context-Free Grammars.
6.3.3 Equivalent Types of Acceptance
6.3.4 Deterministic Pushdown Automata
7 Applications of Models for Context-Free Languages:
Syntax Analysis...
7.1 I ntroduction to Syntax Analysis.
7.1.1 Syntax Specified by Context-Free Grammars.
7.1.2 Top-Down Parsing...
7.1.3 Bottom-Up Parsing..,
7.2 Top-Down Parsing
7.2.1 Predictive Sets and LL Grammars
7.2.1.1 LL Grammars.
7.2.2 Predictive Parsing.
7.2.2.1 Predictive Recursive-Descent Parsing
7.2.2.2 Predictive Table-Driven Parsing.
7.2.2.3 Handling Errors.
7.2.2.4 Exclusion of Left Recursion.
7.3 Bottom-Up Parsing..
7.3.1 Operator-Precedence Parsing
7.3.1.1 Operator-Precedence Parser
7.3.1.2 Construction of Operator-Precedence Parsing
Table.
7.3.1.3 Handling Errors
7.3.1.4 Operator-Precedence Parsers for Other
Expressions
7.3.2 LR Parsing.
7.3.2.1 LR Parsing Algorithm.
7.3.2.2 Construction of LR Table
7.3.2.3 Handling Errors in LR Parsing
8 Properties of Context-Free Langui^es
8.1 Pumping Lemma for Context-Free Languages
8.1.1 Applications of the Pumping Lemma.
8.2 Closure Properties.
8.2.1 Union, Concatenation, and Closure
8.2.2 Intersection and Complement,
8.2.3 Homomorphism
8.2.4 Applications of the Closure Properties
SECTION IV TURING MACHINES AND COMPUTATION
9 Turing Machines and Their Variants.
9.1 Turing Machines and Their Languages.
9.2 Restricted Turing Machines .
9.2.1 Computational Restrictions
9.2.2 Size Restrictions ...
9.3 Universal Turing Machines
9.3.1 Turing Machine Codes
9.3.2 Construction of Universal Turing Machines.
10 Applications of Turing Machines: Iheory of Computation
10.1 Computability.
10.1.1 Integer Functions Computed by Turing
Machines.
10.1.2 Recursion Theorem
10.1.3 Kleene s s-m-n Theorem.
10.2 Decidability
10.2.1 Turing Deciders.
10.2.2 Decidable Problems..
10.2.2.1 Decidable Problems for Finite Automata
10.2.2.2 Decidable Problems for Context-Free Grammars
10.2.3 Undecidable Problems
10.2.3.1 Diagonalization.
10.2.3.2 Reduction
10.2.3.3 Undecidable Problems Not Concerning
Turing Machines
10.2.4 General Approach to Undecidability
10.2.4.1 Rice's Theorem
10.2.5 Computational Complexity.
10.2.5.1 Time Complexity
10.2.5.2 Space Complexity.
11 Turing Machines and General Grammars,
11.1 General Grammars and Their Equivalence with Turing
Machines.
11.1.1 General Grammars
11.1.2 Normal Forms,
11.1.3 Equivalence of General Grammars and Turing Machines.
11.1.3.1 From General Grammars to Turing Machines..
11.1.3.2 From Turing Machines to General Grammars..
11.2 Context-Sensitive Grammars and Linear-Bounded Automata.
11.2.1 Context-Sensitive Grammars and Their Normal Forms.
11.2.1.1 Normal Forms
11.2.2 Linear-Bounded Automata and Their Equivalence with
Context-Sensitive Grammars
11.2.2.1 From Context-Sensitive Grammars to Linear-Bounded
Automata,
11.2.2.2 From Linear-Bounded Automata to Context-Sensitive
Grammars.
11.2.3 Context-Sensitive Languages and Decidable Languages.
11.3 Relations between Language Families
SECTION V CONCLUSION
12 Concluding and Bibliographical Remarks
12.1 Summary.
12.2 Modern Trends.
12.2.1 Conditional Grammars
12.2.2 Regulated Grammars.
12.2.3 Scattered Context Grammars
12.2.4 Grammar Systems
12.3 Bibliographical and Historical Remarks,