Class overview
In this course we'll learn about the theoretical models of computations, their properties and applications. Later we shall look beriefly about the limitations of computation. This course is mathematically oriented and students should have a good background of discrete mathematics and algorithms.
How to find a proof. Proof Techniques - Proof by Induction, Proof by Contradiction, Proof by Construction. Definitions of sets, set operations and languages.
Regular sets and Regular Expression, Non-deterministic and deterministic finite automata and their equivalence, Minimization of deterministic finite automata, Regular expressions to Finite Automata. Finite Automata with outputs. Properties of Regular Sets: Pumping Lemma, Closure Properties, Decision algorithms.
Context Free Grammars. Derivations. Ambiguity in grammars. Chomsky hierarchy of languages and grammars. Regular grammar. Normal Forms for Context free grammars. CNF and GNF. Closure properties of context free languages, Pumping lemma for context free languages. Decision Properties. Pushdown automata.
Context Sensitive Languages: Definition, Examples, Closure Properties, LBA.
Turing machines. Unrestricted Grammars. Properties of recursive and r.e.languages, Undecidability.
The textbooks are the must for learning. Go through that two throughly. I'll use this two mainly in class.
If you get time go through the reference books. Sometimes I'll use the reference books in the class.
The online references include additional problems with solutions (sometimes).
Textbooks:
Automata and Computability- Dexter C. Kozen (1977)
Introduction to the Theory of Computation - Michael Sipser (Third Edition)
References:
Introduction to Automata Theory, Languages and Computation - John E. Hopcroft and Jeffery D. Ulman (1989)
Computability, Complexity and Languages - Martin D. Davis, Ron Sigal and Eliane J. Weyuker (Second Edition)
The Theory of Computation - Bernard M. Moret (First Edition)
An Introduction to Formal Lnguages and Automata - Peter Linz (Fifth Edition)
Introduction to Languages and the Theory of Computation - John C. Martin (Third Edition)
Elements of the Theory of Computation - Harry R. Lewis and Chirstos H. Papadimitriou (Second Edition)
Automata, Computatbility and Complexity: Theory and Applications - Elaine A. Rich (First Edition)
Automata Theory and its Applications - Bakhadyr Khoussainov and Anil Nerode (First Edition)
Online Resources:
Abhijit Das: Misc. ToC Courses
Jeff Ericksion: Misc. ToC Notes and Problems
Continuous Assessment - 15 Marks (7 Home-works)
Midsem Exam - 25 Marks
Endsem Exam - 60 Marks
[Regular Languages : T1|T2|T3|T4]
[Context-free Languages: T5|T6]
[Turing Machines and Effective Computability: T7|T8|T9]
7/1/25:
I'll not take tomorrow's class; next class will be on Monday (13/1/25) 2PM.
All study materials of this week's lectures have been shared with the CR.
Next week first home-work goes out.
15/1/25:
This week' s study materials have been shared.
HW1 is now online. Deadline of submission, 29th January 5PM.
27/1/25:
We have completed the chapter on Regular Languages.
All the study materials on this chapter have been shared.
HW1 and HW2 are on regular languages, both are online.
Tomorrow and day after tomorrow, I'll take tutorials, T3 and T4.
Submit your homeworks in my cabin within the deadline.