Theory of Automata, Formal Languages and Computation

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