Theory of Automata, Formal Languages and Computation

Description

Cover Preface Notations Contents Chapter 0. Introduction 0.1 Basics 0.1.1 Sets 0.1.2 Relations and Functions 0.1.3 Graphs and Trees 0.1.4 Strings and Languages 0.1.5 Boolean Logic 0.1.6 Fundamental Proof Techniques 0.1.7 Introduction to Grammar Glossary Review Questions Exercises Short Questions and Answers Chapter 1. DFA and NFA 1.1 Deterministic Finite Automata (DFA) 1.1.1 Automata—What is it? 1.1.2 Types of Automation 1.1.3 Definition of Deterministic Finite Automation 1.2 Non-Deterministic Finite Automata (NFA) 1.3 Equivalence of NFA and DFA 1.4 Regular Expression 1.4.1 Regular Languages 1.4.2 Regular Expressions 1.4.3 Building Regular Expressions 1.4.4 Languages defined by Regular Expressions 1.4.5 Regular Expressions to NFA 1.4.6 NFAs to Regular Expression 1.5 Two-Way Finite Automata 1.6 Finite Automata with Output 1.6.1 Definition 1.6.2 Mealey Machine 1.6.3 Moore Machine 1.7 Properties of Regular Sets (Languages) 1.7.1 Closure 1.7.2 Union, Concatenation, Negation, Kleene Star, Reverse 1.7.3 Intersection and Set Difference 1.8 Pumping Lemma 1.8.1 Principle of Pumping Lemma 1.8.2 Applying the Pumping Lemma 1.9 Closure Properties of Regular Languages 1.10 Myhill-Nerode Theorem 1.10.1 Myhill-Nerode Relations 1.10.2 Myhill-Nerode Theorem Glossary Review Questions Exercises Short Questions and Answers Chapter 2. Context-Free Grammars 2.1 Introduction 2.1.1 Definition of CFG 2.1.2 Example of CFG 2.1.3 Right-Linear Grammar 2.1.4 Right-Linear Grammars and NFAs 2.1.5 Left-Linear Grammar 2.1.6 Conversion of Left-linear Grammar into Right-Linear Grammar 2.2 Derivation Trees 2.2.1 Definition of a Derivation Tree 2.2.2 Sentential Form 2.2.3 Partial Derivation Tree 2.2.4 Right Most/Left Most/Mixed Derivation 2.3 Parsing and Ambiguity 2.3.1 Parsing 2.3.2 Exhaustive Search Parsing 2.3.3 Topdown/Bottomup Parsing 2.3.4 Ambiguity 2.3.5 Ambiguous Grammars/Ambiguous Languages 2.4 Simplification of CFG 2.4.1. Simplification of CFG-Introduction 2.4.2 Abolishing Useless Productions 2.5 Normal Forms 2.5.1 Chomsky Normal Form (CNF) 2.5.2 Greibach Normal Form Glossary Review Questions Exercises Short-Questions and Answers Chapter 3. Pushdown Automata 3.1 Definitions 3.1.1 Nondeterministic PDA (Definition) 3.1.2 Transition Functions for NPDA 3.1.3 Drawing NPDAs 3.1.4 Execution of NPDA 3.1.5 Accepting Strings with an NPDA 3.1.6. An Example of NPDA Execution 3.1.7 Accepting Strings with NPDA (Formal Version) 3.2 Relationship Between PDA and Context Free Languages 3.2.1 Simplifying CFGs 3.2.2 Normal Forms of Context-Free Grammars 3.2.3 CFG to NPDA 3.2.4 NPDA to CFG 3.2.5 Deterministic Pushdown Automata 3.3 Properties of Context free Languages 3.3.1 Pumping Lemma for CFG 3.3.2 Definitions 3.3.3 Proof of Pumping Lemma 3.3.4 Usage of Pumping Lemma 3.4 Decision Algorithms Glossary Review Questions Exercises Short Questions and Answers Chapter 4. Turing Machines 4.1 Turing Machine Model 4.1.1 What is a Turing Machine? 4.1.2 Definition of Turing Machines 4.1.3 Transition Function, Instantaneous Description and Moves 4.1.4 Programming a Turing Machine 4.1.5 Turing Machines as Acceptors 4.1.6 How to Recognize a Language 4.1.7 Turing Machines as Transducers 4.2 Complete Languages and Functions 4.3 Modification of Turing Machines 4.3.1 N-Track Turing Machine 4.3.2 Semi-infinite Tape/Offline/Multitape/ND Turing Machines 4.3.3 Multidimensional/Two-state Turing Machine 4.4 Church–Turing’s Thesis 4.4.1 Counting 4.4.2 Recursive and Recursively Enumerable Language 4.4.3 Enumerating Strings in a Language 4.4.4 Non-recursively Enumerable Languages 4.5 Undecidability 4.5.1 Halting Problem 4.5.2 Implications of Halting Problem 4.5.3 Reduction to Halting Problem 4.5.4 Post’s Correspondence Problem 4.6 Rice’s Theorem Glossary Review Questions Exercises Short Questions and Answers Chapter 5. Chomsky Hierarchy 5.1 Context Sensitive Grammars and Languages 5.2 Linear Bounded Automata 5.3 Relationship of other Grammars 5.4 The Chomsky Hierarchy 5.5 Extending the Chomsky Hierarchy 5.6 Unrestricted Grammar 5.7 Random-Access Machine Glossary Review Questions Exercises Short Questions and Answers Chapter 6. Computability 6.1 Formal Systems 6.2 Recursive Function Theory 6.3 Primitive Recursive Functions 6.4 Composition and Recursion 6.5 Ackermann’s Function Glossary Review Questions Exercises Short Questions and Answers Chapter 7. Complexity Theory 7.1 Introduction 7.2 Polynomial-Time Algorithms 7.3 Non-Deterministic Polynomial Time Algorithms 7.4 Integer Bin Packing 7.5 Boolean Satisfiability 7.6 Additional NP Problems 7.7 NP-Complete Problems Glossary Review Questions Exercises Short Questions and Answers Chapter 8. Propositions and Predicates 8.1 Propositions 8.1.1 Connectives 8.1.2 Tautology, Contradiction and Contingency 8.1.3 Logical Identities 8.2 Logical Inference 8.3 Predicates and Quantifiers 8.4 Quantifiers and Logical Operators 8.5 Normal Forms Glossary Review Questions Exercises Short Questions and Answers Answers to Exercises University Question Papers Bibliography index