Grade "A+" Accredited by NAAC with a CGPA of 3.46
Placements
Grade "A+" Accredited by NAAC with a CGPA of 3.46
Placements

Theory of Computation

Download Course Details
Course ID
BHCS 12
Level
Undergraduate
Program
B.Sc. CS (Hons.)
Semester
Fifth
Credits
6.0
Paper Type
Core Course
Method
Lecture & Tutorial

Unique Paper Code: Update Awaited

This course introduces formal models of computation, namely, finite automaton, pushdown automaton, and Turing machine; and their relationships with formal languages. Students will also learn about the limitations of computing machines.

Learning Outcomes:

At the end of the course, students should be able to:

  • Design a finite automaton, pushdown automaton or a Turing machine for a problem at hand.
  • Apply pumping lemma to prove that a language is non-regular/non-context-free.
  • Describe limitations of a computing machine.

Course Contents

Unit 1
Unit 2
Unit 3
Unit 4
Unit 5
Unit 6

Unit 1

Languages: Alphabets, string, language, basic operations on language, concatenation, union, Kleene star.

Unit 2

Regular Expressions and Finite Automata: Regular expressions, Deterministic finite automata (DFA).

Unit 3

Regular Languages: Non-deterministic Finite Automata (NFA), relationship between NFA and DFA, Transition Graphs (TG), properties of regular languages, the relationship between regular languages and finite automata, Kleene’s Theorem.

Unit 4

Non-Regular Languages and Context Free Grammars: Pumping lemma for regular grammars, Context-Free Grammars (CFG),

Unit 5

Context-Free Languages (CFL) and PDA: Deterministic and non-deterministic Pushdown Automata (PDA), parse trees, leftmost derivation, pumping lemma for CFL, properties of CFL.

Unit 6

Turing Machines and Models of Computations: Turing machine as a model of computation, configuration of simple Turing machine, Church Turing Thesis, Universal Turing Machine, decidability, halting problem.

Additional Information

Text Books


Cohen, D. I. A. (2011). Introduction to Computer Theory. 2nd edition. Wiley India.
Lewis, H.R. & Papadimitriou, H. R. (2002). Elements of the Theory of Computation. 6th edition. Prentice Hall of India (PHI)

Additional Resources


Goodrich, M., Tamassia, R., & Mount, D.M. (2011). Data Structures and Algorithms Analysis in C++. 2nd edition. Wiley.
Gopalkrishnan, G.L. (2019) Automata and Computability: A programmer’s perspective. CRC Press.
Linz, P. (2016). An Introduction to Formal Languages and Automata.6th edition. Jones and Bartlett Learning.

Teaching Learning Process


Use of ICT tools in conjunction with traditional class room teaching methods
Interactive sessions
Class discussions

Assessment Methods

Written tests, assignments, quizzes, presentations as announced by the instructor in the class

Keywords

Regular expressions and languages, finite automata, context free grammar and languages, pushdown automata, Turing machine.

Disclaimer: Details on this page are subject to change as per University of Delhi guidelines. For latest update in this regard please refer to the University of Delhi website here.