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