# Department of computer science and engineering

 Название Department of computer science and engineering Дата 06.10.2012 Размер 61.4 Kb. Тип Документы

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:

1. To have an understanding of finite state and pushdown automata.

2. To have a knowledge of regular languages and context free languages.

3. To know the relation between regular language, context free language and corresponding recognizers.

4. To study the Turing machine and classes of problems

Learning Outcome and End use:

Students should be able to:

1. Identify the fundamentals of the problem in finite automata.

2. Acquire a broad understanding of the regular languages and expression.

3. Have general ideas about context free grammar with a various relationship regular languages.

4. Be familiar with a Turing machine and properties of Context Free Languages.

5. 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,2nd Edition, 2000

R2 - John Martin C, Introduction to languages and the Theory of Computation, McGraw Hill, 2nd Edition,1997

Web Resources :

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 e-moves T1(22 - 25) 1 6 6 Equivalence of regular expression and NFA with e-moves T1(27 - 41) 1 7 7 Pumping lemma for regular sets T1(41-44) 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, NP-complete T1(281 - 295) 2 37 25 Tutorial 3 40 UNIT V UNSOLVABLE PROBLEMS 26 Unsolvable problems R1(177-179) 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 e-moves

• 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

## Похожие:

Разместите кнопку на своём сайте:
Библиотека

База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека