Department of Computer Science and Engg. Kalasalingam University, Krishnankoil 626190
KALASALINGAM UNIVERSITY, ANAND NAGAR, KRISHNANKOIL – 626 190
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
COURSE PLAN
Name of the staff : Mr.B.Pitchai Manickam Subject with code : Theory of Computation (CSE 5011) Course : M.Tech Semester / Branch : I / CSE
Prerequisite:
Students should 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 language, context free language and corresponding recognizers. To study the Turing machine and classes of problems
Learning Outcome and End use:
Students should be able to:
Identify the fundamentals of the problem in finite automata. Acquire a broad understanding of the regular languages and expression. Have general ideas about context free grammar with a various relationship regular languages. Be familiar with a Turing machine and properties of Context Free Languages. Understanding the concepts in undecidability problems.
List of Text Book:
T1  Natarajan A.M, Tamilarasi A and Balasubramani P, Theory of Computation, New age International publishers, 2002.
Reference book(s):
R1  Hopcroft and Ullman, Introduction to Automata, Languages and Computation Narosa Publishers,2^{nd} Edition, 2000 R2  John Martin C, Introduction to languages and the Theory of Computation, McGraw Hill, 2^{nd }Edition,1997
Web Resources :
http://infolab.stanford.edu/~ullman/ialc.html. http://www.comp.nus.edu.sg/~sanjay/cs323.html http://www.cse.iitb.ac.in/~supratik/curses/cs331/index.html http://www.cit.gu.edu.au/~rwt/toc.02.2/ http://www.cs.ucc.ie/~dgb/courses/toc.html
Lesson Plan:
Topic No  Topic Name  Page No.  No.of Periods  Cumulative No.of Periods  UNIT I FINITE AUTOMATA AND REGULAR LANGUAGES  1  Finite Automata and Regular languages  T1 (1  10)
 1  1  2  Regular expressions and Regular languages  T1(10  15)  2  3  3  Non deterministic finite automata and Kleenes theorem  T1(11  18)  1  4  4  Equivalence of DFA and NFA  T1(19  22)  1  5  5  Finite Automation with emoves  T1(22  25)  1  6  6  Equivalence of regular expression and NFA with emoves  T1(27  41)  1  7  7  Pumping lemma for regular sets  T1(4144)  1  8  8  Tutorial 
 3  11  UNIT II CONTEXT FREE LANGUAGES  9  Context free languages  T1(100  102)  1  12  10  Derivation and languages  T1(102  108)  2  14  11  Relationship between derivation and derivation trees  T1(109  116)  2  16  12  Simplification of context free grammars  T1(116  126)  2  18  13  Normal forms for context free grammars, CNF, and GNF.  T1(127  136)  2  20  14  Tutorial 
 3  23  UNIT III PUSH DOWN AUTOMATA (PDA)  15  Acceptance by PDA  T1(166  177)  1  24  16  Pushdown automata and Context free languages  T1(178 185)  2  26  17  Pumping lemma for CFL  T1(186  192)  1  27  18  Deterministic Context free languages, Deterministic pushdown automata.  T1(193 – 201)  1  28  19  Tutorial 
 3  31  UNIT IV TURING MACHINE  20  Context sensitive languages and LBA  T1(341  345)  1  32  21  Turing machine (Definition and examples)  T1(255  258)  1  33  22  Computable languages and functions  T1(259  263)  1  34  23  Church Turing hypothesis, Universal Turing machine.  T1(279  280)  1  35  24  P and NP problems, NPcomplete  T1(281  295)  2  37  25  Tutorial 
 3  40  UNIT V UNSOLVABLE PROBLEMS  26  Unsolvable problems  R1(177179)  1  41  27  Rice Theorem  R1(185 192)  2  43  28  Post's correspondence Problem  R1(193  201)  2  45  29  Recursive and recursively enumerable languages.  T1(328 335)  2  47  30  Tutorial 
 3  50 
Portions for Monthly Test I, II and III:

S.No  Test  Topic No.  1  I  1  14  2  II  15 – 25  3  III  26 – 30 
Seminar Topics: Minimization of FSA. Moore and mealy machines. Application of Regular expression. Algebric Laws for Regular Languages. Decision Properties of Regular languages and CFL. Normal form of Context free grammars. LR(0) Grammar, Parsing. Extension of Turing machine. Closure properties of Regular set and CFL.
Related Books and Magazines/Journals
Programming Exercises.
Implementation of to search a string in a text using the DFA and NFA. Implementation of Converting DFA to NFA Implementation of minimizing the DFA Implementation of constructing a parse tree Implementation of converting the Regular expression to NFA with emoves Implementation of converting automata to Regular expression.
Tutorials
Converting DFA’s to Regular expression by eliminating states. Converting Regular expression to Automata. Constructing a parse tree Convert a CFG to PDA accepted by a empty stack. Normal form of Context free grammars.
Prepared By Verified By
(HOD/CSE)
Our Mission: To Produce Technically Competent, Socially Committed, And Readily Employable Computer Engineers By Offering Quality Education and Research
