Anna University , Chennai
Department of B.E-Computer Science and Engg
Fifth Semester
CS6503 Theory of Computation
Lecture Notes
(Regulation 2013)
UNIT-I FINITE AUTOMATAIntroduction
Basic Mathematical Notation and Techniques
Finite State systems
Basic Definitions
Finite Automaton
DFA and NDFA
Finite Automaton with € moves
Regular Languages
Regular Expression
Equivalence of NFA and DFA
Equivalence of NDFA with and without € moves
Equivalence of Finite Automaton and RE
Minimization of DFA
Pumping lemma for Regular sets
Problems based on Pumping lemma
UNIT -II GRAMMARS
Grammar Introduction
Types of Grammar
Context Free Grammars and Languages
Derivations and Languages
Ambiguity
Relationship between derivation and
derivation trees
Simplification of CFG
Elimination of Useless symbols
Unit productions
Null Productions
Greibach Normal Form
Chomsky normal form
Problems related to CNF and GNF
UNIT-III PUSHDOWN AUTOMATA
Pushdown automata(PDA)
Definitions
Moves
Instantaneous descriptions
Deterministic pushdown automata
Problem solving in Pushdown automata
Equivalence of pushdown automata and CFL
Pumping lemma for CFL
Problems based on Pumping lemma
UNIT - IV TURING MACHINES
Definitions of TM
Models
Computable languages and functions
Techniques for TM construction
Multi head and Multi tape TM
The Halting problem
Partial Solvability
Problems about TM
Chomskian hierarchy of languages
UNIT 5 : UNSOLVABLE PROBLEMS AND COMPUTABLE
FUNCTIONS
Unsolvable problems and Computable
Functions
Primitive recursive functions
Recursive and recursively enumerable
languages
Universal TM
Measuring and Classifying Complexity.
Tractable and Intractable problems
Tractable and possibly Intractable problems
P and NP completeness
Polynomial time reductions
Attachment :
CS6503 - Theory of Computation (TOC) Notes.pdf (Size: 4.03 MB / Downloads: 18,941)
Share your Study Materials with us : 