# CS6503 Theory of Computation Lecture Notes

0

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
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,939)