DOC/LP/01/28.02.02
/ LESSON PLAN / LP-CS2303LP: Rev. No: 00
Date: 25-06-2010
Page 1 of 6
Sub Code & Name : CS2303- THEORY OF COMPUTATION
Unit : I Branch : CS Semester : V
UNIT I - AUTOMATA9
Introduction to formal proof – Additional forms of proof – Inductive proofs –FiniteAutomata (FA) – Deterministic Finite Automata (DFA) – Non-deterministic FiniteAutomata (NFA) – Finite Automata with Epsilon transitions.
Objective: This Unit introduces about the different types of formal proof and about Finite Automata. It also gives a deep insight about the Deterministic Finite Automata and the Non-deterministic FiniteAutomata with and without Epsilon transitions with theorems.
SessionNo / Topics to be covered / Time in min / Ref / Teaching Method
1 / Introduction to Theory of Computation and Automata Theory / 50 / T1 / BB
2 / Introduction to formal proof – Deductive Proof, Reduction to Definitions, Other forms, Not to be If-then statements / 50 / T1 / BB
3 / Additional forms of proof – Proving equivalence about sets, Contrapositive, Proof by Contradiction, Counterexamples / 50 / T1 / BB
4 / Inductive Proofs – Induction on Integers, Structural Forms, Mutual Induction / 50 / T1 / BB
5 / Central Concepts of Automata Theory, Informal Picture of Finite Automata / 50 / T1 / BB
6,7 / Deterministic finite Automata – Definitions, Processing Strings, Notations, Transition Functions, Languages of DFA and problems / 100 / T1 / BB
8,9 / Non-deterministic Finite Automata – Definition, Transition Function, Languages of NFA, Equivalence of NFA and DFA and problems / 100 / T1 / BB
10 / Finite Automata with Epsilon transitions – Uses, Notation, Epsilon-closures, Extended transitions
and languages / 50 / T1 / BB
11,12 / Eliminating Epsilon-Transitions, Theorem and problems / 100 / T1 / BB
DOC/LP/01/28.02.02
/ LESSON PLAN / LP-CS2303LP: Rev. No: 00
Date: 25-06-2010
Page 2 of 6
Sub Code & Name : CS2303- THEORY OF COMPUTATION
Unit : II Branch : CS Semester : V
UNIT II – REGULAR EXPRESSIONS AND LANGUAGES9
Regular Expression – FA and Regular Expressions – Proving languages not to beregular – Closure properties of regular languages – Equivalence and minimization ofAutomata.
Objective: This Unit introduces Regular Expressions and Conversion of RE to DFA and vice-versa. It also explains about how to prove a language not to be a regular language. Finally it deals with testing equivalence of regular languages and Minimization of DFA’s.
SessionNo / Topics to be covered / Time in min / Ref / Teaching Method
13 / Regular Expression – Introduction, Building RE, Precedence of Regular Expression operators / 50 / T1 / BB
14,15 / Finite Automata & Regular Expressions – Converting DFA to RE and problems / 100 / T1 / BB
16,17 / Converting RE to DFA and problems / 100 / T1 / BB
18,19 / Proving Languages not to be Regular – Pumping Lemma and its Applications and problems / 100 / T1 / BB
20 / Closure properties of regular Languages / 50 / T1 / BB
21 / Closure properties of regular Languages / 50 / T1 / BB
22 / Testing Equivalence of sets and states / 50 / T1 / BB
23,24 / Minimization of Automata and problems / 100 / T1 / BB
CAT I / 75
DOC/LP/01/28.02.02
/ LESSON PLAN / LP-CS2303LP: Rev. No: 00
Date: 25-06-2010
Page 3 of 6
Sub Code & Name : CS2303- THEORY OF COMPUTATION
Unit : III Branch : CS Semester : V
UNIT III – CONTEXT FREE GRAMMARS AND LANGUAGES9
Context-Free Grammar (CFG) – Parse Trees – Ambiguity in grammars and languages –Definition of the Pushdown automata – Languages of a Pushdown Automata –Equivalence of Pushdown automata and CFG– Deterministic Pushdown Automata.
Objective: This Unit introduces Context Free Grammar and Parse Tree. It also deals with ambiguity in grammars and language. It also introduces Pushdown Automata and its languages and its equivalence with CFG.
SessionNo / Topics to be covered / Time in min / Ref / Teaching Method
25,26 / Context Free Grammars – Informal example, Definition, Derivations, Language of a Grammar and problems / 100 / T1 / BB
27,28 / Parse trees – construction, Yield, Inference, Derivations and problems / 100 / T1 / BB
29,30 / Ambiguity in Grammars and Languages – Ambiguous Grammars, Removing Ambiguity, Inherent Ambiguity and problems / 100 / T1 / BB
30,31 / Pushdown Automata – Definition, Graphical notation,Instantaneous Descriptions and problems / 100 / T1 / BB
32 / Languages of a PDA – Acceptance by Final state and empty stack, empty stack to final state & vice versa / 50 / T1 / BB
33 / Equivalence of PDA’s and CFG’s / 50 / T1 / BB
34,35 / Deterministic Pushdown Automata – Definition, DPDA’s and Regular Languages & CFL’s and problems / 100 / T1 / BB
DOC/LP/01/28.02.02
/ LESSON PLAN / LP-CS2303LP: Rev. No: 00
Date: 25-06-2010
Page 4 of 6
Sub Code & Name : CS2303- THEORY OF COMPUTATION
Unit : IV Branch : CS Semester : V
UNIT IV – PROPERTIES OF CONTEXT-FREE LANGUAGES9
Normal forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – TuringMachines – Programming Techniques for TM.
Objective: This Unit introduces the various Normal forms for CFG and also deals with Pumping Lemma for Context Free Languages and its closure properties. It also gives in depth knowledge about Turing Machine and its Programming Techniques.
SessionNo / Topics to be covered / Time in min / Ref / Teaching Method
36 / Normal forms for CFG-Eliminating Useless Symbols, Eliminating epsilon productions and problems / 50 / T1 / BB
37 / Eliminating Unit productions and Chomsky Normal forms and problems / 50 / T1 / BB
38 / Pumping Lemma for CFL-Statement and Applications / 50 / T1 / BB
39 / Closure properties of CFL / 50 / T1 / BB
40,41 / Introduction to Turing Machine-Notation, Instantaneous Descriptions and Transition diagram and problem / 50 / T1 / BB
42 / Programming Techniques for TM-Storage in the State / 50 / T1 / BB
43 / Programming Techniques for TM-Multiple Tracks / 50 / T1 / BB
44 / Programming Techniques for TM-Subroutines / 50 / T1 / BB
45,46 / Problems on Programming Techniques for TM / 100 / T1 / BB
47 / Extensions of Basic TM / 50 / T1 / BB
48 / Non-deterministic TM / 50 / T1 / BB
CAT II / 75
DOC/LP/01/28.02.02
/ LESSON PLAN / LP-CS2303LP: Rev. No: 00
Date: 25-06-2010
Page 5 of 6
Sub Code & Name : CS2303- THEORY OF COMPUTATION
Unit : V Branch : CS Semester : V
UNIT V – UNDECIDABILITY9
A language that is not Recursively Enumerable (RE)–An undecidable problem that isRE- Undecidable problems about Turing Machine – Post’s Correspondence Problem –The classes P and NP.
Objective: This Unit introduces Recursive and Recursively Enumerable Languages. It also introduces about Decidable and Undecidable Problems, Undecidable Problems that is Recursively Enumerable, Undecidable problems about TM. It also introduces Post’s Correspondence Problem and The classes P and NP.
SessionNo / Topics to be covered / Time in min / Ref / Teaching Method
49 / A language that is not Recursively Enumerable – Coding for TM, Diagonalization Language / 50 / T1 / BB
50 / An undecidable problem that isRE – Recursive Languages, Complements / 50 / T1 / BB
51 / Universal Language, Undeciadability of Universal Language / 50 / T1 / BB
52 / Undecidable problems about Turing Machine – Reductions / 50 / T1 / BB
53 / TM accepting Empty Language
54 / Rice’s Theorem and Properties of the RE Languages / 50 / T1 / BB
55 / Post’s Correspondence Problem – Definition and problems / 50 / T1 / BB
56 / Modified PCP and problems / 50 / T1 / BB
57 / The Classes of P and NP – Problems solvable in Polynomial Time with examples / 50 / T1 / BB
58 / Nondeterministic Polynomial Time with examples / 50 / T1 / BB
59 / Polynomial-Time Reductions / 50 / T1 / BB
60 / NP-complete problems / 50 / T1 / BB
CAT III / 75
/ LESSON PLAN / LP-CS2303
LP: Rev. No: 00
Date: 25-06-2010
Page 6 of 6
Sub Code & Name : CS2303- THEORY OF COMPUTATION
Branch : CS Semester : V
DOC/LP/01/28.02.02
Week / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II
Units / 1 / 1 / 1 / 1 / 1 / 1 / 2 / 2 / 2 / 2 / 2 / 2 / 3 / 3 / 3 / 3 / 3 / 3
4 / 4 / 4 / 4 / 4 / 4 / 4 / 5 / 5 / 5 / 5 / 5 / 5
Course Delivery Plan
BOOKS FOR STUDY
TEXT BOOKS
1. J.E. Hopcroft, R. Motwani and J.D. Ullman, “Introduction to Automata Theory,Languages and Computations”, second Edition, Pearson Education, 2007.
REFERNCES
1.H.R. Lewis and C.H. Papadimitriou, “Elements of the theory of Computation”,Second Edition,
Pearson Education, 2003.
2. Thomas A. Sudkamp,” An Introduction to the Theory of Computer Science,Languages and
Machines”, Third Edition, Pearson Education, 2007.
3. Raymond Greenlaw an H.James Hoover, “ Fundamentals of Theory of Computation,Principles
and Practice”, Morgan Kaufmann Publishers, 1998.
4. Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Brokecole,1997.
5. J. Martin, “Introduction to Languages and the Theory of computation”Third Edition, Tata Mc
Graw Hill, 2007
Prepared by / Approved bySignature
NameDesignation / Ms. R.Gayathri / Lecturer
Ms.G.Janakasudha / Lecturer / Dr.Susan Elias
HOD, Department of CS
Date / 25-06-2010