Scribd
Upload
78 views2 pages

Topic

The document outlines the lesson plan for the Theory of Computation course at Mysore College of Engineering & Management for the 5th semester of the academic year 2024-25. It includes topics such as Pushdown Automata, Context-Free Grammars, and Turing Machines, with a total of 25 hours of instruction. The course aims to equip students with skills in automata theory, regular languages, CFGs, PDAs, Turing machines, and concepts of decidability.

Uploaded by

janaki reddy
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
78 views2 pages

Topic

The document outlines the lesson plan for the Theory of Computation course at Mysore College of Engineering & Management for the 5th semester of the academic year 2024-25. It includes topics such as Pushdown Automata, Context-Free Grammars, and Turing Machines, with a total of 25 hours of instruction. The course aims to equip students with skills in automata theory, regular languages, CFGs, PDAs, Turing machines, and concepts of decidability.

Uploaded by

janaki reddy
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/ 2

MYSORE COLLEGE OF ENGINEERING & MANAGEMENT, MYSURU

(Affiliated to VTU, Belagavi, Approved by AICTE, New Delhi & Govt. Of Karnataka)
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
Lesson Plan - ODD Semester [Academic Year: 2024-25]

Semester: 5th No. of Hours: 25


Subject Name: Theory of Computation Subject Code: BCS503
Faculty Name: Prof. Janaki Reddy D

Hr. Plan Date Topic Actual Date Mode of


delivery
Module - 3
1 Definition of the Pushdown Automaton.
2 The Language of a PDA.
3 Equivalence of PDA’s and CFG’s. Chalk and
4 talk
5 Deterministic Pushdown Automata.
6
Module - 4
7 Normal Forms for Context Free Grammars.
8
9 The Pumping Lemma for Context Free Language Chalk and
10 talk
11 Closure Properties of Context Free Language
Module - 5
12 Introduction to Turing Machines: Problems That
Computers Cannot Solve.
13 The Turing Machine
14 Programming Techniques for Turing Machines,
15 Chalk and
16 Extensions to the Basic Turing Machine talk
17
18
19 Undecidability: A Language That Is Not Recursively
20 Enumerable.

Course outcome (Course Skill Set) At the end of the course, the student will be able to:
1. Apply the fundamentals of automata theory to write DFA, NFA, Epsilon-NFA and conversion between
them.
2. Prove the properties of regular languages using regular expressions.
3. Design context-free grammars (CFGs) and pushdown automata (PDAs) for formal languages.
4. Design Turing machines to solve the computational problems.
5. Explain the concepts of decidability and undecidability.
Reference:
1. Elain Rich, “Automata,Computability and complexity”, 1st Edition, Pearson Education,2018.
2. K.L.P Mishra, N Chandrashekaran , 3rd Edition , ‘Theory of Computer Science”,PHI,2012.
3. Peter Linz, “An introduction to Formal Languages and Automata “, 3rd Edition, Narosa Publishers,1998.
4. Michael Sipser : Introduction to the Theory of Computation, 3rd edition, Cengage learning,2013.
5. John C Martin, Introduction to Languages and The Theory of Computation, 3rd Edition, Tata McGraw –Hill
Publishing Company Limited, 2013.

Faculty Signature HOD Signature

You might also like