[go: up one dir, main page]
Scribd
Upload
43 views6 pages

CS8501 - TOC - Lesson Plan 2022-23

Uploaded by

vjay2003
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
43 views6 pages

CS8501 - TOC - Lesson Plan 2022-23

Uploaded by

vjay2003
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

PERI Institute of Technology

Mannivakkam, Chennai 600048


Department of Computer Science and Engineering
Degree and Programme B.E/ CSE
Semester V
Course Code and Name: CS8501/Theory of Computation
Core / Elective: Core
LTPC 3003 No. of Credits: 3
Date of commencement: 10.08.2022

Faculty Incharge: Mr.Vijayanarayanan

Definition:
Theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how
efficiently they can be solved or to what degree.
Course objective:
● To understand the language hierarchy
● To construct automata for any given pattern and find its equivalent regular expressions
● To design a context free grammar for any given language
● To understand Turing machines and their capability
● To understand undecidable problems and NP class problems
Course Outcomes:
Students will be able to

 Construct automata, regular expression for any pattern.


 Write Context free grammar for any construct.
 Design Turing machines for any language.
 Propose computation solutions using Turing machines.
 Derive whether a problem is decidable or not
SYLLABUS
CS8501 Theory of Computation
(Regulation 2017)
LTPC:3003

UNIT I AUTOMATA FUNDAMENTALS 9


Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic Finite Automata – Non-
deterministic Finite Automata – Finite Automata with Epsilon Transitions

UNIT II REGULAR EXPRESSIONS AND LANGUAGES 9


Regular Expressions – FA and Regular Expressions – Proving Languages not to be regular – Closure Properties of Regular Languages
– Equivalence and Minimization of Automata.

UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES 9


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.

UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES 9


Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines – Programming Techniques for
TM.

UNIT V UNDECIDABILITY 9
Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Post‘s
Correspondence Problem, The Class P and NP.
TOTAL: 45 PERIODS
TEXT BOOKS:
1. J.E.Hopcroft, R.Motwani and J.D Ullman, ―Introduction to Automata Theory, Languages and Computations‖, Second Edition,
Pearson Education, 2003.
REFERENCES:
1. H.R.Lewis and C.H.Papadimitriou, ―Elements of the theory of Computation‖, Second Edition,PHI2003.
2. J.Martin, ―Introduction to Languages and the Theory of Computation‖, Third Edition, TMH, 2003.
3. Micheal Sipser, ―Introduction of the Theory and Computation‖, Thomson Brokecole, 1997.

OS1-https://nptel.ac.in/courses/106104148
OS2-https://www.youtube.com/watch?v=rKCAPVaU0Qk
OS3-https://www.youtube.com/watch?v=jN8zvENdjBg
OS4- https://youtu.be/phOlq9SuscM
OS5-https://youtu.be/MzhiVE6OuQA
OS6-https://youtu.be/0pMm_QxCg3I?t=3
OS7-https://youtu.be/Mo01x0LPxio
OS8- https://youtu.be/eKySjjLZKF0
OS9- https://youtu.be/ZxPuzNDG2fo
OS10- https://youtu.be/mpQZVYPuDGU?t=23
Cognitive
Use Of Reference Remarks
S. Proposed Actual Teaching
Topic to be Covered Level
Teaching Material
No Date Date Methodolgy
Tool
UNIT I AUTOMATA FUNDAMENTALS
1. Introduction to formal BB Lecture
18.08.2021 20.08.2021 Understand T1,R1
Proofs
Additional forms of
2. Visual lecture T1,R1 OS1
Proof 19.08.2021 23.08.2021 Remember
Aids, PPT
Additional forms of
3. Apply BB Lecture T1,R1
Proof 20.08.2021 24.08.2021

4. 25.08.2021 Apply BB Lecture T1,R2


Inductive Proofs 23.08.2021
Finite Automata– Lecture with
5. Understand BB T1,R2
Deterministic Finite 24.08.2021 26.08.2021 demonstration
Automata
Finite Automata–
6. Understand BB Lecture T1,R3
Deterministic Finite 25.08.2021 27.08.2021
Automata
7. Non-deterministic Finite Visual Lecture with T1,R1
26.08.2021 30.08.2021 Apply OS2
Automata Aids, PPT demonstration

T1,R1
8. Non-deterministic Finite Apply BB Lecture
27.08.2021 01.09.2021
Automata
Finite Automata with OS3
9. Apply BB/PPT Lecture T1,R1
Epsilon Transitions 30.08.2021 02.09.2021

UNIT II REGULAR EXPRESSIONS AND LANGUAGES

10. Regular Expressions 01.09.2021 05.09.2021 Remember BB Lecture T1,R1

Lecture with
11. FA and Regular 02.09.2021 06.09.2021 Understand
Visual
demonstration
T1,R1
Expressions Aids, PPT

12. FA and Regular 05.09.2021 07.09.2021 Understand BB Lecture T1,R1


Expressions

13. Proving Languages not 06.09.2021 08.09.2021 Understand BB Lecture T1,R2


to be regular
Lecture with
Maping of Content Beyond Syllabus with PO’s and PSO’s
S.No Unit Topics Mapping with PO’s and PSO’s
1 V Lexical Analyzer PO1,PO2,PO3,PSO1

2 V Natural language Processing PO1,PO2,PO3,PO12,PSO3

Staff Incharge HOD/CSE Vice Principal

You might also like