Rajalakshmi Engineering College

RAJALAKSHMI ENGINEERING COLLEGE Thandalam, Chennai – 602 105 LESSON PLAN

Faculty Name Subject Name Year Degree & Branch

:

BENEDICT JAYAPRAKASH

Staff Code

:

CS40

: : :

NICHOLAS THEORY OF COMPUTATION III B.E. – C.S.E.

Subject Code Semester Section

: : :

CS1303 V A

Aim:  To have an introductory knowledge of automata, formal language theory and computability. Objectives:  To have an understanding of finite state and pushdown automata.  To have a knowledge of regular languages and context free languages.  To know the relation between regular languages and context free languages and their corresponding recognizers.  To study the Turing Machine and classes of problems. Text Book(s): 1. J.E.Hopcroft, R.Motwani and J.D Ullman,“Introduction to Automata Theory, Languages and Computations”, Second Edition, Pearson Education, 2003. Reference Book(s): 1. J.Martin, “Introduction to Languages and the Theory of Computation”, Third Edition, TMH, 2003. 2. H.R.Lewis and C.H.Papadimitriou, “Elements of The Theory of Computation”, Second Edition,Pearson Education/PHI, 2003. 3. Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Brokecole, 1997. 4. J.E. Hopcroft and J.D Ullman, “Introduction to Automata Theory, Languages and Computations, Narosa. Sl. No. 1

Date

Period

Unit

18-06-2008

I

I

Introduction to TOC

I

Finite Automaton

2

Topic(s)

Signature of Faculty

T / R*

Book

Book

No.

T

1

Signature of HOD 1

Page(s) 25-30

Sl. No.

Date

Period

Unit

Topic(s)

3

I

Deterministic Finite Automaton

4

I

Problems on DFA

5

I

Problems on DFA

6

I

Non-deterministic FA

7

I

Problems on NFA

8

I

Problems on NFA

9

I

Equivalence of NFA & DFA

10

I

Conversion of NFA to DFA

11

I

FA with Epsilon Transitions

12

I

Equivalence of NFA with & without Epsilon moves

13

I

Problems on Conversion of NFA’s to DFA’s

14

I

Introduction to formal proofs

15

I

Additional forms of proofs

16

II

Regular Expressions

17

II

Equivalence of FA & regular expressions

18

II

Equivalence of FA & regular expressions

19

II

Problems on conversion of regular expression to NFA

20

II

Problems on conversion of DFA to regular expression

21

II

Pumping Lemma

Signature of Faculty

T / R*

Book

Book

No.

Signature of HOD 2

Page(s)

Sl. No.

Date

Period

Unit

Topic(s)

22

II

Problems on Pumping Lemma

23

II

Closure properties of regular sets

24

II

Closure properties of regular sets

25

II

Equivalence & Minimization of Automata

26

II

Equivalence & Minimization of Automata

27

II

Problems on Minimization

28

III

Context Free Grammars

29

III

Derivation Trees

30

III

Problems on design of CFG

31

III

Problems on design of CFG

32

III

Parse Trees

33

III

Ambiguity in grammars

34

III

Push down Automata

35

III

The languages of a PDA

36

III

The languages of a PDA

37

III

Problems on PDA

38

III

Problems on PDA

39

III

Equivalence of PDA & CFG

40

III

Problems on conversion of PDA To CFG & vice-versa

41

III

Problems on conversion of PDA To CFG & vice-versa

Signature of Faculty

T / R*

Book

Book

No.

Signature of HOD 3

Page(s)

Sl. No.

Date

Period

Unit

Topic(s)

42

III

Deterministic PDA

43

IV

Normal forms for CFG

44

IV

Problems on CNF

45

IV

Pumping Lemma for CFL

IV

Closure properties of CFL

IV

Closure properties of CFL

IV

Turing Machines

IV

Transition Diagrams for TM

IV

Problems on TM

IV

Problems on TM

IV

TM Programming techniques

V

Recursively Enumerable Lang.

V

Undecidable problems

V

Undecidable problems

V

Undecidable problems & TM

V

Rice Theorems

V

Post Correspondence Problem

V

The classes P and NP

T / R*

Book

Book

No.

* T  Text Book / R  Reference Book

Signature of Faculty

Signature of HOD 4

Page(s)