This book provides an in-depth analysis of classical automata theory, including finite automata, pushdown automata, and Turing machines. It also covers current trends in automata theory, such as jumping, deep pushdown, and regulated automata. The book strikes a balance between a theoretical and practical approach to its subject by presenting many real world applications of automata in a variety of scientific areas, ranging from programming language processing through natural language syntax analysis up to computational musicology.In Automata: Theories, Trends and Applications all formalisms concerning automata are rigorously introduced, and every complicated mathematical passage is preceded by its intuitive explanation so that even complex parts of the book are easy to grasp. The book also demonstrates how automata underlie several computer-science engineering techniques.This monograph is a useful reference for scientists working in the areas of theoretical computer science, computational mathematics, computational linguistics, and compiler writing. It may also be used as a required text in classes dealing with the theory and applications of automata, and theory of computation at the graduate level. This book comes with access to a website which supplies supplementary material such as exercises with solutions, additional case studies, lectures to download, teaching tips for instructors, and more.
Author(s): Alexander Meduna; Tomas Kozar
Publisher: World Scientific Publishing
Year: 2023
Language: English
Pages: 437
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
