Automata. Theory, Trends and Applications

Contents
Preface
	Subject
	Use of the Book
	Structure of the Book and its Synopsis
	Support
About the Authors
Acknowledgments
Part 1 Introduction
	1. Terminology
		Mathematical Background
		1.1 Logic
		1.2 Sets and Languages
			Languages
		1.3 Relations and Translations
		1.4 Graphs
	2. Automata
		2.1 Automata as Models of Computation
		2.2 Automata as Language Models
Part 2 Theory
	3. Finite Automata
		An Introductory Example
		3.1 Definitions
			Representations of finite automata
		3.2 Restrictions
			Removal of ε-rules
		3.3 Determinism
			Complete specification
			Minimization
		3.4 Regular Expressions
			Regular expressions
			Equivalence with FAs
			From FAs to REs
			From REs to FAs
			Pumping lemma for regular languages
			Applications of the pumping lemma for regular languages
	4. Pushdown Automata
		An Introductory Example
		4.1 Definitions
			Equivalent types of acceptance
		4.2 Determinism
	5. Turing Machines
		An Introductory Example
		5.1 Definitions
		5.2 Restrictions
			Computational restrictions
			Size restrictions
		5.3 Universality
			Turing machine codes
			Construction of universal Turing machines
	6. Automata and Their Grammatical Equivalents
		6.1 Context-Free Grammars and Pushdown Automata
			Restricted context-free grammars
			Canonical derivations and derivation trees
			Leftmost derivations
			Rightmost derivations
			Derivation trees
			Ambiguity
			Removal of useless symbols
			Removal of erasing rules
			Removal of single rules
			Chomsky normal form
			Elimination of left recursion
			Greibach normal form
			Equivalence with pushdown automata
			From context-free grammars to pushdown automata
			From pushdown automata to context-free grammars
			Applications of the pumping lemma
		6.2 General Grammars and Turing Machines
			Normal forms
			Equivalence of general grammars and Turing machines
			From general grammars to Turing machines
			From Turing machines to general grammars
			Context-Sensitive Grammars and Linear-Bounded Automata
			Context-sensitive grammars and their normal forms
			Normal forms
			Linear-bounded automata and their equivalence with context-sensitive grammars
			From context-sensitive grammars to linear-bounded automata
			From linear-bounded automata to context-sensitive grammars
			Language Family Relationships
		6.3 Making Context-Free Grammars Stronger
			State grammars
			Scattered context grammars
	7. A Metaphysics of Computation
		An Introductory Example
		7.1 Computability
			Integer functions computed by TMs
			Recursion theorem
			Kleene’s s-m-n Theorem
		7.2 Decidability
			Turing deciders
			Decidable problems for finite automata
			Decidable problems for context-free grammars
			Undecidable Problems
			Diagonalization
			Reduction
			Undecidable problems not concerning Turing machines
			A general approach to undecidability
			Rice’s theorem
		7.3 Complexity
			Time complexity
			Space complexity
Part 3 Trends
	8. Regulated Automata
		8.1 Self-Regulating Automata
			Self-regulating finite automata
			Accepting power
			n-turn first-move self-regulating finite automata
			n-turn all-move self-regulating finite automata
			Language families accepted by n-first-SFAs and n-all-SFAs
			Self-regulating pushdown automata
			Accepting power
			Open problems
		8.2 Automata Regulated by Control Languages
			Finite automata regulated by control languages
			Definitions
			Conversions
			Regular-controlled finite automata
			Context-free-controlled finite automata
			Pushdown automata regulated by control languages
			Definitions
			Regular-Controlled Pushdown Automata
			Linear-Controlled Pushdown Automata
	9. Jumping Automata
		9.1 Definitions and Examples
			Denotation of language families
		9.2 Accepting Power
		9.3 Properties
			Decidability
			An Infinite Hierarchy of Language Families
			Left and Right Jumps
		9.4 A Variety of Start Configurations
			A summary of open problems
	10. Deep Pushdown Automata
		10.1 Definitions and Examples
		10.2 Accepting Power
			Determinism
			Generalization
Part 4 Applications
	11. Applications of Automata
		11.1 Finite Automata and Lexical Analysis
			Implementation of finite automata
			A table-based implementation
			A case-statement implementation
			Introduction to lexical analysis
			Lexical units and regular expressions
			Scanners and finite automata
			Implementation of a scanner
		11.2 Pushdown Automata and Syntax Analysis
		11.3 Syntax Specified by Context-Free Grammars
			Top-Down Parsing
			Bottom-Up Parsing
		11.4 Top-Down Parsing
			Predictive sets and LL grammars
			LL grammars
			Predictive parsing
			Predictive recursive-descent parsing
			Predictive table-driven parsing
			Exclusion of Left Recursion
		11.5 Bottom-Up Parsing
			Operator-precedence parsing
			Construction of operator-precedence parsing table
			Operator-precedence parsers for other expressions
			LR parsing
			LR parsing algorithm
			Construction of LR table
	12. Applications of Grammars
		12.1 Natural Language Processing
			Syntax and related linguistic terminology
			Introduction through examples
			Terminology
			Verbs
			Personal pronouns
			Transformational scattered context grammars
			Scattered context in English syntax
			Clauses with neither and nor
			Existential clauses
			Interrogative clauses
			Question tags
			Generation of grammatical sentences
		12.2 Musicology
			Basics of musical notation
			Context-free music: Arch dependencies
			Retrogradation
			Scattered context music: Serial dependencies
			Transposition
			Sequence
			Contrary motion
			Augmentation
			Diminution
Part 5 Conclusion
	13. Summary
	14. Historical and Bibliographical Remarks
		The Twentieth Century
		The Twenty-First Century
About the Supplementary Website
Bibliography
Index