Subject Name Theory of computation
Course Type (Core/Elective) PCC(Core)
Subject Code Credits 3
Scheme (L-T-P) 2-1-0 Instruction 2 Hours/week (L)
1 Hours/week (T)
1. Objective of the course: This course is about the machine construction logic. It is core computer
science paper and good for system level engineers.
2. Outcome of the course: Students will get exposure of machine creation mechanism, language
construction etc.
3. Course Plan: As per the below format only
Unit Topics for Coverage
Unit 1 Regular languages: Notion of a formal language, DFAs and notion for their acceptance, informal
and formal definitions. Class of regular languages, Closure of the class under complementation,
union and intersection. Strategy for designing DFAs, Pumping lemma for regular languages,
NFAs. Notion of computation trees. Definition of languages accepted. Construction of
equivalent DFAs of NFAs. NFAs with epsilon transitions, Regular expressions, Closure
properties for regular languages, States minimization of DFAs,
Unit 2 Context free languages: Notion of grammars and languages generated by grammars.
Equivalence of regular grammars and finite automata. Context free grammars and their parse
trees. Context free languages. Ambiguity, Elimination of useless symbols, epsilon productions,
unit productions from CFGs. Chomsky normal form, Pumping lemma for CFLs and its use.
Closure properties of CFLs, Decision problems for CFLs.
Unit 3 Pushdown automata (PDAs): deterministic and nondeterministic. Instantaneous descriptions
of PDAs. Language acceptance by final states and by empty stack. Equivalence of PDAs and
CFGs,
Unit 4 Turing machines: Recursively enumerable languages, Turing machines (TMs)-their
instantaneous descriptions. Language acceptance by TMs, Types of TMs, Church-Turing
hypothesis and its foundational implications, Codes for TMs. Recursively enumerable (r.e.) and
recursive languages. Existence of non-r.e. languages. Notion of undecidable problems.
Universal language and universal TM. Separation of recursive and r.e. classes.
4. Text Book:
a. Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft , Rajeev
Motwani , Jeffrey D. Ullman
5. References:
a. Introduction to the theory of Computation by Michael Sipser,
b. An Introduction to Formal Languages and Automata by Peter Linz
