Elementary Computability, Formal Languages, and Automata

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0005.djvu
PREFACE......Page __sk_0013.djvu
1.1 "Algorithm" Defined......Page __sk_0017.djvu
1.1.1 Questions and Problems......Page __sk_0018.djvu
1.1.2 The Definition......Page __sk_0019.djvu
1.1.4 Further Discussion......Page __sk_0022.djvu
1.1.5 Three Similar Definitions......Page __sk_0024.djvu
1.1.6 Related Concepts......Page __sk_0026.djvu
1.2.1 Algorithms from Our Childhood......Page __sk_0028.djvu
1.2.2 The Euclidean Algorithm......Page __sk_0030.djvu
1.2.3 A Labyrinth Algorithm......Page __sk_0031.djvu
1.2.4 Labyrinth Algorithm: Discussion......Page __sk_0034.djvu
1.3.1 The Theory of Computability......Page __sk_0036.djvu
1.3.2 Formal Languages and Automata......Page __sk_0038.djvu
2.1.1 The Model......Page __sk_0039.djvu
2.1.2 Total Configurations; Computations......Page __sk_0041.djvu
2.1.3 Copying......Page __sk_0043.djvu
2.1.4 Nonnegative Integers......Page __sk_0044.djvu
2.1.5 Iteration......Page __sk_0047.djvu
2.1.6 Exercises......Page __sk_0049.djvu
2.2 The Universal Turing Machine......Page __sk_0051.djvu
2.2.2 Coded Quintuples......Page __sk_0052.djvu
2.2.3 Coded Configurations......Page __sk_0054.djvu
2.2.4 The Stored-Program Computer......Page __sk_0056.djvu
3. The Foundational Programming Languages......Page __sk_0057.djvu
3.1.1 Informal Description......Page __sk_0058.djvu
3.1.2 Exposition of the Syntax......Page __sk_0059.djvu
3.1.3 Discussion......Page __sk_0060.djvu
3.2.1 Basic Exposition......Page __sk_0063.djvu
3.2.2 Time Cycles; Run Histories......Page __sk_0065.djvu
3.2.3 Unsuitability for Practical Programming......Page __sk_0067.djvu
3.3.1 Syntax......Page __sk_0068.djvu
3.3.2 Elementary Semantics......Page __sk_0070.djvu
3.3.3 A Sample Run......Page __sk_0072.djvu
3.3.5 Exercises......Page __sk_0073.djvu
3.4 Flowcharts......Page __sk_0074.djvu
3.4.1 Schematic and Detailed Flowcharts......Page __sk_0075.djvu
3.4.2 Multiplication......Page __sk_0076.djvu
3.4.3 What a Program Does......Page __sk_0079.djvu
3.4.4 Exercises......Page __sk_0080.djvu
3.5.1 Subtraction......Page __sk_0083.djvu
3.5.2 Square Root......Page __sk_0085.djvu
3.6.1 Functions......Page __sk_0088.djvu
3.6.2 Examples; Discussion......Page __sk_0089.djvu
3.6.3 Program Verification......Page __sk_0090.djvu
3.6.4 Multiplication Program Verified......Page __sk_0091.djvu
3.7.1 A New Command......Page __sk_0094.djvu
3.7.2 Discussion; Examples......Page __sk_0096.djvu
3.7.3 Exercises......Page __sk_0098.djvu
4.1 Explicit Definition and Primitive Recursion......Page __sk_0100.djvu
4.1.1 Explicit Definition......Page __sk_0101.djvu
4.1.2 Primitive Recursion......Page __sk_0103.djvu
4.1.3 The Formalism of Functional Expressions......Page __sk_0105.djvu
4.2.1 Some More Definitions......Page __sk_0107.djvu
4.2.2 Definition by Cases......Page __sk_0109.djvu
4.2.3 Quotient and Remainder......Page __sk_0111.djvu
4.2.4 Summary List of Functions......Page __sk_0112.djvu
4.2.5 Exercises......Page __sk_0114.djvu
4.3.1 The Function Phi_4......Page __sk_0117.djvu
4.3.2 A Family of Functions......Page __sk_0119.djvu
4.3.3 The Function Defined by Ackermann......Page __sk_0120.djvu
4.3.4 The Ackermann-Peter function......Page __sk_0122.djvu
4.3.5 Programmability of AP......Page __sk_0124.djvu
4.3.6 Exercises......Page __sk_0126.djvu
4.4.1 A New Definition Scheme......Page __sk_0127.djvu
4.4.2 More Examples......Page __sk_0130.djvu
4.4.3 Partial Functions......Page __sk_0132.djvu
4.4.4 Fermat's Last Theorem......Page __sk_0133.djvu
4.4.5 Exercises......Page __sk_0135.djvu
4.5 Programs for Defined Functions......Page __sk_0137.djvu
4.5.1 Explicit Definition......Page __sk_0138.djvu
4.5.2 Primitive Recursion......Page __sk_0139.djvu
4.5.3 Mu Recursion......Page __sk_0141.djvu
4.5.4 Programs and Function Definitions......Page __sk_0142.djvu
4.5.5 Exercises......Page __sk_0143.djvu
4.6.1 The Rules of Computation......Page __sk_0144.djvu
4.6.2 Formal Computations Defined......Page __sk_0146.djvu
4.6.3 Some Helpful Propositions......Page __sk_0148.djvu
4.7.1 Some Previously Defined Functions......Page __sk_0149.djvu
4.7.2 New Examples......Page __sk_0150.djvu
4.7.3 Equational Definitions and Algorithms......Page __sk_0152.djvu
4.7.4 Definitive Equations......Page __sk_0153.djvu
4.7.5 Exercises......Page __sk_0156.djvu
4.8.1 Importance of the Class......Page __sk_0157.djvu
4.8.2 More Facts About the Class......Page __sk_0159.djvu
4.8.3 The Class of Computable Functions......Page __sk_0161.djvu
4.8.4 Closing Remarks for Chapter 4......Page __sk_0162.djvu
4.8.5 Exercises......Page __sk_0163.djvu
5.1.1 Prospectus......Page __sk_0164.djvu
5.1.2 Finite Sequences of Positive Integers......Page __sk_0165.djvu
5.1.3 Gödel Numbers of Strings, etc.......Page __sk_0167.djvu
5.1.4 Gödel Numbers of Graphs......Page __sk_0168.djvu
5.1.5 Gödel Numbers and Data Structures......Page __sk_0170.djvu
5.2.1 The Gödel Number of a GOTO Program......Page __sk_0171.djvu
5.2.2 The Gödel Number of a Computation......Page __sk_0173.djvu
5.2.3 The Function Computed by a Program......Page __sk_0174.djvu
5.2.4 A Universal GOTO Program......Page __sk_0176.djvu
5.3.1 The Argument......Page __sk_0178.djvu
5.3.2 Discussion......Page __sk_0180.djvu
6. Unsolvable Problems......Page __sk_0183.djvu
6.1.1 Self-Convergence......Page __sk_0184.djvu
6.1.2 Generalizing the Result......Page __sk_0185.djvu
6.1.3 Other Formalisms......Page __sk_0186.djvu
6.2.1 Halting from an All-Zero Input......Page __sk_0188.djvu
6.2.2 The Undecidability of Totality......Page __sk_0190.djvu
6.2.3 Turing Machines and Semi-Thue Systems......Page __sk_0192.djvu
6.2.4 The Transformation Problem for Semi-Thue Systems......Page __sk_0195.djvu
6.2.5 Semigroups......Page __sk_0196.djvu
6.2.6 An Undecidable Word Problem......Page __sk_0198.djvu
6.2.7 Et Cetera......Page __sk_0199.djvu
7.1 An Example and the Definition......Page __sk_0201.djvu
7.1.1 The Concept......Page __sk_0202.djvu
7.1.2 Derivations and Derivation Trees......Page __sk_0204.djvu
7.1.3 Nonterminals Versus Syntactic Categories......Page __sk_0206.djvu
7.1.4 The Definition......Page __sk_0207.djvu
7.1.5 Further Discussion......Page __sk_0209.djvu
7.2 Grammars for Some Significant Languages......Page __sk_0211.djvu
7.2.1 The Full Formalism of Functional Expressions......Page __sk_0212.djvu
7.2.3 The GOTO Language......Page __sk_0214.djvu
7.2.4 Propositional Calculus with Parentheses......Page __sk_0215.djvu
7.2.5 Parenthesis-Free Propositional Calculus......Page __sk_0217.djvu
7.2.6 Exercises......Page __sk_0220.djvu
7.3.1 Subgrammars as Subgoals......Page __sk_0221.djvu
7.3.2 Further Examples......Page __sk_0223.djvu
7.3.3 Formulas for Certain Strings......Page __sk_0226.djvu
7.3.4 Exercises......Page __sk_0228.djvu
7.4.1 Lambda Productions......Page __sk_0231.djvu
7.4.2 Noncontracting Productions......Page __sk_0234.djvu
7.4.3 Exercises......Page __sk_0235.djvu
7.5 The Dispensability of Lambda Productions......Page __sk_0236.djvu
7.5.1 Lambda-Yielding Nonterminals......Page __sk_0237.djvu
7.5.2 Constructing G_1 and G_2......Page __sk_0238.djvu
7.5.3 An Example......Page __sk_0239.djvu
7.5.4 The Equivalence of G_0 and G_1......Page __sk_0240.djvu
7.5.5 Justifying the Algorithm......Page __sk_0241.djvu
7.5.6 Further Remarks......Page __sk_0243.djvu
7.5.7 Exercises......Page __sk_0244.djvu
8.1.1 Eighth-Grade Parsing......Page __sk_0245.djvu
8.1.2 Lexical and Structural Ambiguities......Page __sk_0247.djvu
8.1.3 The Derivation Tree As a Parse......Page __sk_0248.djvu
8.1.4 Isomorphism of Derivation Trees......Page __sk_0249.djvu
8.2.1 The Utility of Parentheses......Page __sk_0251.djvu
8.2.2 Unambiguous Grammars for Fixed Languages......Page __sk_0253.djvu
8.2.3 Precedence of Operators......Page __sk_0254.djvu
8.2.4 Operator Precedence and Parsing......Page __sk_0255.djvu
8.2.5 Examplesfor Finding Equivalent Unambiguous Grammars......Page __sk_0257.djvu
8.2.6 More Examples......Page __sk_0260.djvu
8.2.7 Exercises......Page __sk_0262.djvu
8.3.1 Mating Operations......Page __sk_0264.djvu
8.3.2 Some Theorems About Mating......Page __sk_0265.djvu
8.3.3 The Unambiguity of G-IN......Page __sk_0267.djvu
8.3.4 A Parsing Method for G-IN......Page __sk_0269.djvu
8.4.1 The Unambiguity of G-PRE......Page __sk_0272.djvu
8.4.2 A Parsing Methodfor G-PRE......Page __sk_0275.djvu
8.4.3 Top-Down Parsing......Page __sk_0277.djvu
8.4.4 Perfectly Univocal Grammars......Page __sk_0279.djvu
8.4.5 Exercises......Page __sk_0281.djvu
8.5 A Nondeterministic Parsing Automaton......Page __sk_0283.djvu
8.5.1 Parsing in Practice......Page __sk_0284.djvu
8.5.2 The Scan-k Parsing Automaton......Page __sk_0285.djvu
8.5.3 A Sample History......Page __sk_0287.djvu
8.5.5 Rightmost Derivations......Page __sk_0290.djvu
8.5.6 The Main Theorem......Page __sk_0293.djvu
8.6 The Deterministic Parsing Automaton......Page __sk_0295.djvu
8.6.1 D Functions......Page __sk_0296.djvu
8.6.2 The Functions D_p,k......Page __sk_0298.djvu
8.6.3 Other Examples Using D_p,k......Page __sk_0299.djvu
8.6.4 Using the Input Head......Page __sk_0300.djvu
8.6.5 Efficiency of Suffix Notation......Page __sk_0301.djvu
8.6.6 Designing a Suitable Grammar......Page __sk_0302.djvu
8.6.7 Exercises......Page __sk_0304.djvu
8.7.1 Limited Power of the Present Model......Page __sk_0306.djvu
8.7.2 Nondeterministic Languages......Page __sk_0308.djvu
8.7.3 Formula Evaluation......Page __sk_0309.djvu
8.7.4 Translation of Formal Languages......Page __sk_0311.djvu
8.7.5 A Sample Translation......Page __sk_0312.djvu
8.7.6 General Formulation......Page __sk_0314.djvu
9.1.1 Graphical Representation......Page __sk_0316.djvu
9.1.2 Transition Graphs......Page __sk_0319.djvu
9.1.3 Some Examples......Page __sk_0320.djvu
9.1.4 Exercises......Page __sk_0323.djvu
9.2 Finite Automata......Page __sk_0324.djvu
9.2.2 The State Graph......Page __sk_0326.djvu
9.2.3 The Nondeterministic Finite Automaton......Page __sk_0327.djvu
9.2.4 Transition Graphs into State Graphs......Page __sk_0328.djvu
9.2.5 Second Version of the Algorithm......Page __sk_0331.djvu
9.2.6 An Example and a Theorem......Page __sk_0332.djvu
9.2.7 Simplification of State Graphs......Page __sk_0333.djvu
9.2.8 Some Theorems......Page __sk_0335.djvu
9.2.9 Exercises......Page __sk_0336.djvu
9.3 Regular Expressions......Page __sk_0338.djvu
9.3.1 Syntax and Semantics......Page __sk_0339.djvu
9.3.2 Some Valid Equations......Page __sk_0341.djvu
9.3.3 Some Examples......Page __sk_0342.djvu
9.3.4 The Expression-to-Graph Algorithm......Page __sk_0343.djvu
9.3.5 An Example......Page __sk_0345.djvu
9.3.6 More Theorems......Page __sk_0346.djvu
9.3.7 The Graph-to-Expression Algorithm......Page __sk_0348.djvu
9.3.8 An Example; Theoretical Discussion......Page __sk_0349.djvu
9.3.9 Exercises......Page __sk_0351.djvu
9.4 Languages That Are Not Regular......Page __sk_0352.djvu
9.4.2 The Proof Generalized......Page __sk_0353.djvu
9.4.3 Using Other Theorems......Page __sk_0354.djvu
9.4.4 Languages Not Context-Free......Page __sk_0355.djvu
9.4.5 Exercises......Page __sk_0356.djvu
Appendix I. Euclidean Algorithm: Correctness Proof......Page __sk_0358.djvu
Appendix II. Labyrinth Algorithm: Correctness Proof......Page __sk_0361.djvu
AIII.l Natural and Formal Languages......Page __sk_0365.djvu
AIII.2 Strings Over an Alphabet......Page __sk_0366.djvu
AIII.3 A Sample Formal Language......Page __sk_0368.djvu
AIII.4 Syntax and Semantics......Page __sk_0370.djvu
AIII.5 Pragmatics; Imperatives......Page __sk_0372.djvu
AIII.6 The Semantics of Commands......Page __sk_0373.djvu
AIV.l Static Criteria......Page __sk_0376.djvu
AIV.3 Computational Complexity......Page __sk_0378.djvu
AIV.4 Complexity and Algorithm Selection......Page __sk_0380.djvu
AIV.5 Efficiency of the Euclidean Algorithm......Page __sk_0382.djvu
AIV.6 Number of Times in the Loop......Page __sk_0384.djvu
AIV.7 Efficiency of a Competing Algorithm......Page __sk_0386.djvu
A V.l Simple Induction......Page __sk_0388.djvu
A V.2 Course-of-Values Induction......Page __sk_0390.djvu
A V.3 Proofs About Trees......Page __sk_0391.djvu
A VI.1 A Famous Proof by Georg Cantor......Page __sk_0394.djvu
A VI.2 Russell's Paradox......Page __sk_0395.djvu
A VI.3 The Epimenides Paradox......Page __sk_0397.djvu
A VI.4 A Recursive Function Not Primitive-Recursive......Page __sk_0398.djvu
A VI.5 Computational Complexity......Page __sk_0400.djvu
A VI.6 Space Complexities......Page __sk_0402.djvu
Bibliography......Page __sk_0404.djvu
Index of Symbols......Page __sk_0411.djvu
Index......Page __sk_0413.djvu