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 :


  1. http://infolab.stanford.edu/~ullman/ialc.html.

  2. http://www.comp.nus.edu.sg/~sanjay/cs323.html

  3. http://www.cse.iitb.ac.in/~supratik/curses/cs331/index.html

  4. http://www.cit.gu.edu.au/~rwt/toc.02.2/

  5. 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 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



Похожие:

Department of computer science and engineering iconDepartment of Computer Science and Engineering

Department of computer science and engineering iconDepartment of Electrical Engineering and Computer Science

Department of computer science and engineering iconDepartment of Computer Science and Information Engineering

Department of computer science and engineering iconDepartment of Computer Science and Information Engineering

Department of computer science and engineering iconT. Kasetkasem and P. K. Varshney Department of Electrical Engineering and Computer Science Syracuse University Syracuse, ny 13244

Department of computer science and engineering iconGeological Engineering Department The Geology chair was, first, estabilished within the Department of Natural Science in Faculty of Science of Ege University, on October 4, 1961

Department of computer science and engineering iconIn Electrical Engineering and Computer Science Massachusetts Institutes of Technology, August 1986. Member of Computational Structures Group at Laboratory of Computer Science, mit, June 1982 to August 1986. Ms

Department of computer science and engineering iconComputer Engineering Department

Department of computer science and engineering iconDepartment of Computer Science

Department of computer science and engineering iconThe Department of Computer Science 3

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


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