CS6503 Theory of Computation Lecture Notes

[Srini]

   

Anna University , Chennai

Department of B.E-Computer Science and Engg

Fifth Semester

CS6503 Theory of Computation

Lecture Notes

(Regulation 2013) 

UNIT-I  FINITE AUTOMATA
Introduction   
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)