The course gives an overview over basic formal grammars and abstract machine models used in Computer Science. In particular, finite automata, pushdown automata, context-free grammars and Turing machines are studied with respect to  their properties and limits. Based on Turing machines the concepts of decidability and recursive enumerability are introduced.

Pre-requisites

  • Discrete Mathematics

Post Conditions

  1. The student is able to describethe basic computational models FAs, PDAs, grammars and Turing machines.
  2. The student is able to formally model a given computational problem and prove its correctness.
  3. The student can explain the concepts of undecidability and recursive enumerability and is able to give examples of respective problems.

Textbook

  • Introduction to the theory of computation by Michael Sipser (3rd Ed.) - Indian Edition (there is an ebook available online which is slightly different)
  • (Reference) Hopcroft/Motwani/Ullman: Introduction to Automata Theory, Languages, and  Computation (Pearson Education 2009)

Office Hours

 InstructorWalk-in or prior appointment by email
 Tanmay Garg
Monday 2-3pm MTech lab
 Aashay Mittal
Monday 10-11pm (night) Boys hostel common room
 Anant Jain
Wednesday 5:30-6:30pm Boys hostel common room
 Dheeraj Singh
Thursday 1:30-2:30 MTech lab
 Manpreet Kaur
Thursday 6-7pm MTech lab
 ShanuFriday 1:30-2:30pm MTech lab