图书简介

1 ; AUTOMATA, FORMAL LANGUAGES AND COMPUTABILITY; 1.1 Formal Languages; 1.1.1 Phrase Structure Grammars; 1.2 Chomsky Classification of Grammars; 1.3 Computability; Supplementary Examples; A Quick Review; Problems for Practice; Objective Type Questions; 2 ; MATHEMATICAL PRELIMINARIES; 2.1 Set Theory; 2.2 Relations; 2.2.1 Types of Relations; 2.3 Functions; 2.4 Counting Techniques; 2.4.1 Permutations; 2.4.2 Combinations; 2.4.3 Pigeonhole Principle; 2.5 Logic; 2.5.1 Propositions and Logic; 2.6 Methods of Proof; 2.6.1 Direct Proof; 2.6.2 Indirect Proof; Supplementary Examples; A Quick Review; Problems for Practice; Objective Type Questions; 3 ; FINITE AUTOMATA; 3.1 Finite Automata; 3.1.1 String processing by finite automaton; 3.2 Properties of transition function; 3.3 Deterministic and Nondeterministic Finite Automaton; 3.3.1 Acceptance of a string by NFA; 3.4 Equivalence of NFA and DFA; 3.4.1 Converting a NFA to equivalent DFA; 3.4.2 Equivalence of DFAs; 3.5 Level Equivalence and Reduction in Finite Automaton; 3.6 Finite automata with outputs; 3.6.1 Moore and Mealy Machines; 3.6.2 Conversion of a Moore Machine to equivalent Mealy Machine; 3.6.3 Conversion of a Mealy Machine to equivalent Moore Machine; 3.7 Finite automata with null moves; 3.7.1 Removal of null moves; Supplementary Examples; A Quick Review; Problems for Practice; Objective Type Questions; 4 ; REGULAR SETS AND REGULAR GRAMMAR; 4.1 Regular Expression; 4.2 Correspondence between regular expression and regular set; 4.3 Identities related to regular expressions; 4.4 Relation between Regular Languages and Finite Automata; 4.4.1 Finite automaton corresponding to regular expression; 4.4.2 Regular expression corresponding to finite automaton; 4.5 Closure properties of regular sets; 4.6 Automata for union, intersection and difference of languages; 4.7 Pumping Lemma for regular Languages; 4.7.1 Applications of pumping lemma; 4.7.2 Suitability of pumping lemma; 4.8 Production System associated with regular grammar; 4.9 Myhill Nerode Theorem (Equivalent Classes and Regular Languages); 4.10 Some Decision Problems related to Finite Automata and Regular Langauges; 4.11 Regular language and current programming language scenario; Supplementary Examples; A Quick Overview; Problems for Practice; Objective Type Questions; 5 ; CONTEXT FREE GRAMMARS AND LANGUAGES; 5.1 Some example recursive grammars; 5.2 Context Free Grammars; 5.2.1 Leftmost and Rightmost Derivation of a string; 5.2.2 Some example context free languages and grammars; 5.2.3 Ambiguity in Context Free Grammar and Parse Tree; 5.2.4 Possible defects in CFG and their removal; 5.2.4.1 Failure of non terminal(s) to generate terminal(s); 5.2.4.2 Problem of unit productions; 5.2.4.3 Problem of unreachable non terminal; 5.2.4.4 Problem of null productions; 5.3 Context Free languages as superset of regular languages; 5.4 Closure properties of Context Free languages; 5.4.1 Intersection of a CFL and a regular language; 5.5 Normal Forms for CFGs; 5.5.1 Chomsky Normal Form; 5.5.2 Greibach Normal Form; 5.6 Pumping lemma for Context Free Grammars; 5.6.1 Applications of pumping lemma; 5.7 More on closure properties; 5.7 Applications of Context Free Grammars; 5.7.1 Programming language Constructs; 5.7.2 Natural Language; 5.7.3 Markup Languages; Supplementary Examples; A Quick Overview; Problems for Practice; Objective Type Questions; 6 ; PUSHDOWN AUTOMATA; 6.1 Basic Structure of Pushdown Automata; 6.2 Two types of acceptance by PDA; 6.3 Correspondence between PDA and CFL; 6.3.1 PDA corresponding to a given CFG; 6.3.2 CFG corresponding to a given PDA; 6.4 Parsing and PDA; 6.4.1 Design of Top Down Parser; 6.4.2 Design of a Bottom up Parser; Supplementary Examples; A Quick Overview; Problems for Practice; Objective Type Questions; 7 ; TURING MACHINES; 7.1 Basic structure and working of a Turing Machine; 7.2 Instantaneous Description of a Turing Machine; 7.3 Language of a Turing machine; 7.4 Turing Machine as computer for positive integers; 7.5 Universal Turing machine (UTM); 7.5.1 UTM and Modern Day Computer; 7.6 Enhancements in Turing Machine; 7.6.1 Multi-track Turing Machine; 7.6.2 Multi-tape Turing Machine; 7.7 Turing Machine as Enumerator; 7.8 Non-Deterministic and Deterministic Turing machine; 7.9 lternative representations of Turing Machines; 7.9.1 Turing Machine with semi infinite Tape; 7.9.2 Two stack machine; 7.10 Time and Space Complexity of a Turing Machine; 7.11 Some other machines; 7.11.1 Linear Bound Automata; 7.11.2 Post Machine; Supplementary Examples; A Quick Overview; Problems for Practice; Objective Type Questions; 8 ; THE PITFALL OF ALGORITHMIC COMPUTING: UNDECIDABILITY; 8.1 Recursive and Non Recursive Languages; 8.2 Language of Turing machines; 8.3 Some decision problems relating to Turing Machines; 8.4 Some Decision Problems relating to CFG; 8.5 Post Correspondence Problem; 8.5.1 Constructing CFG using PCP; Supplementary Examples; A Quick Overview; Problems for Practice; Objective Type Questions; 9 ; COMPUTABLE FUNCTIONS; 9.1 Primitive Recursive Functions; 9.2 m Recursive Functions; 9.2.1 Computability and m Recursive Functions; Supplementary Examples; A Quick Overview; Problems for Practice; Objective Type Questions; 10 ; COMPUTATIONAL COMPLEXITY: TRACTABLE AND POSSIBLY INTRACTABLE PROBLEMS; 10.1 Growth Rates of Functions; 10.2 Languages and complexity classes; 10.3 Decision Problems and Optimization Problems; 10.4 The classes P and NP; 10.5 NP Complete Problems; 10.6 Significance of discovering NP complete problems; 10.7 Some misconceptions about NP-complete problems; Supplementary Examples; A Quick Overview; Problems for Practice; Objective Type Questions; APPENDIX A; Church-Turing hypothesis; APPENDIX B; Godel Numbering; APPENDIX C; Homage to key scientists in the field of automata theory and computation; APPENDIX D; Chronology of Some Important Events

Trade Policy 买家须知