## Notes on Computation Theory

Download Notes on Computation Theory, This course is an introduction to the theory of Computation. Topics covered includes: Background mathematics, Models of Computation, Context-Free Grammars, Automata, The Chomsky Hierarchy. Download pdf from below to explore all topics.

CONTENTS-

1 Introduction
1.1 Why Study Theory?
1.2 Overview
1.2.1 Computability
1.2.2 Context-Free Grammars
1.2.3 Automata
2 Background Mathematics
2.1 Some Logic
2.2 Some Sets
2.2.1 Functions
2.3 Alphabets and Strings
2.3.1 Strings
2.4 Languages
2.5 Proof
2.5.1 Review of proof terminology
2.5.2 Review of methods of proof
2.5.3 Some simple proofs
2.5.4 Induction
3 Models of Computation
3.1 Turing Machines
3.1.1 Example Turing Machines
3.1.2 Extensions
3.1.3 Coding and Decoding
3.1.4 Universal Turing machines
3.2 Register Machines
3.3 The Church-Turing Thesis
3.3.1 Equivalence of Turing and Register machines
3.4 Recognizabilty and Decidability
3.4.1 Decidable problems about Turing machines
3.4.2 Recognizable problems about Turing Machines
3.4.3 Closure Properties
3.5 Undecidability
3.5.1 Diagonalization
3.5.2 Existence of Undecidable Problems
3.5.3 Other undecidable problems
3.5.4 Unrecognizable languages
4 Context-Free Grammars
4.1 Aspects of grammar design
4.1.1 Proving properties of grammars
4.2 Ambiguity
4.3 Algorithms on CFGs
4.3.1 Chomsky Normal Form
4.4 Context-Free Parsing
4.5 Grammar Decision Problems
4.6 Push Down Automata
4.7 Equivalence of PDAs and CFGs
4.7.1 Converting a CFG to a PDA
4.7.2 Converting a PDA to a CFG
4.8 Parsing
5 Automata 145
5.1 Deterministic Finite State Automata
5.1.1 Examples
5.1.2 The regular languages
5.1.3 More examples
5.2 Nondeterministic finite-state automata
5.3 Constructions
5.3.1 The product construction
5.3.2 Closure under union
5.3.3 Closure under intersection
5.3.4 Closure under complement
5.3.5 Closure under concatenation
5.3.6 Closure under Kleene star
5.3.7 The subset construction
5.4 Regular Expressions
5.4.1 Equalities for regular expressions
5.4.2 From regular expressions to NFAs
5.4.3 From DFA to regular expression
5.5 Minimization
5.6 Decision Problems for Regular Languages
5.6.1 Is a string accepted/generated?
5.6.2 L(M) = ∅?
5.6.3 L(M) = Σ∗?
5.6.4 L(M1) ∩ L(M2) = ∅?
5.6.5 L(M1) ⊆ L(M2)?
5.6.6 L(M1) = L(M2)?
5.6.7 Is L(M) finite?
5.6.8 Does M have as few states as possible?
6 The Chomsky Hierarchy
6.1 The Pumping Lemma for Regular Languages
6.1.1 Applying the pumping lemma
6.1.2 Is L(M) finite?
6.2 The Pumping Lemma for Context-Free Languages
7 Further Topics
7.1 Regular Languages
7.1.1 Extended Regular Expressions
7.1.2 How to Learn a DFA
7.1.3 From DFAs to regular expressions (Again)
7.1.4 Summary