Annexure ‘CD – 01’
L T P/S SW/FW No. of TOTAL
PSDA CREDIT
Course Title: Theory of Computation Credit Units: 04 UNITS
3 - - 2 3 04
Course Level: UG Course Code:
CSE204
Course Objectives: The course begins with the basic mathematical preliminaries and goes on to discuss the general theory of automata, properties of regular
sets and regular expressions, and the basics of formal languages. Besides, sufficient attention is devoted to such topics as pushdown automata and it’s relation
with context free languages, Turing machines and linear bounded automata, the basic concepts of computability such as primitive recursive functions and
partial recursive functions.
Pre-requisites: Mathematical Basics: familiarity with proofs, discrete math and algorithms.
Course Contents/Syllabus:
Weightage (%)
Module I: Introduction to Languages and Automata
Formal Grammars and Chomsky Hierarchy, Regular Expression Deterministic and Nondeterministic Finite Automata,
Regular Expression, Regular Expression to Finite Automata and vice versa, Arden’s Theorem , Two way Finite
25
Automata, Finite Automata with output, Properties of regular sets, pumping lemma for regular sets, My-Hill-Nerode
Theorem .
Module II: Context Free Grammars and Pushdown Automata
CFG: Formal Definition, Derivation and Syntax trees, Simplification Forms, Ambiguous Grammar, Properties of CFL,
Normal Forms (CNF and GNF), Pushdown Automata: Definitions, Relationship between PDA and context free 25
language, Decision Algorithms
Module III: Turing Machine 25
The Turing Machine Model, Language acceptability of Turing Machine, Design of TM, Variation of TM, Universal
TM, Church’s Machine. Recursive and recursively enumerable language, unrestricted grammars, Context Sensitive
Language, Linear Bounded Automata (LBA).
Module IV: Un-decidability
Turing machine halting Problem, undecidable problems for recursive enumerable language, Post correspondence
15
problems (PCP) and Modified Post correspondence problems, Undecidable problems for CFL.
Module V: Computability
Partial and Total Functions, Primitive Recursive functions, Recursive functions. 10
Course Learning Outcomes:
At the end of this course, the student will be able to
Familiarity with basics of Formal Languages, Grammars, Automata and their relationship.
Design regular expressions and context-free grammars accepting or generating a certain language.
Transform between equivalent deterministic and non-deterministic finite automata, and regular expressions.
Design Push Down Automata, Equivalence of PDA to CFG and vice-versa.
Designing of Turing machines to solve problems
Classification of a Problem as decidable and undecidable.
Have an overview of how the theoretical study in this course is applicable to an engineering application like designing the compilers
Pedagogy for Course Delivery:
This is an introductory graduate level course to the theory of computation. We will briefly discuss in lectures finite and push-down
automata, and regular and context-free languages and practice problems will be discussed in tutorials. We will then focus on the
fundamental mathematical model of a Turing Machine, discuss its powers and limitations. The course will be delivered online
with the help of e-contents using videos, online resources, quiz etc.
List of Professional Skill Development Activities:
1. Quiz
2. Case Study
3. Group Presentation
Assessment/ Examination Scheme:
Theory L/T (%) Lab/Practical/Studio (%)
100 ---
Theory Assessment (L&T):
Continuous Assessment/Internal Assessment 40% End Term Examination
60%
Components (Drop down) Attendance Class Test Assignment Viva Group Quiz EE
Presentation
Linkage of PSDA with 3 3 10
Internal Assessment
Component, if any
Weightage (%) 5 15 4 60
Text Reading:
1. K.L.P. Mishra and N.Chandrasekaran, “Theory of Computer Science : Automata, Languages and Computation”, PHI.
References:
1. Introduction to theory of computation by Michael sipser.
2. An introduction to formal languages and Automata by Peter Linz, Narosa Publication Papadimitrou, C. and Lewis, C.L., “Elements of the Theory of
Computation”, PHI
3. Martin J. C., “Introduction to Languages and Theory of Computations”, TMH
4. Hopcroft and Ullman, “Introduction to Automata Theory, languages and computation”, Addision Wesley.
5. Formal Languages and Automata Theory by C.K Nagpal
