Formal languages and computation: models and their applications/
Alexander Meduna
- Boca Raton: CRC Press, 2014.
- xix, 295 p. : ill. ; 27 cm.
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,