The course gives an overview over basic formal grammars and abstract machine models used in Computer Science. In particular, finite automata, pushdown automata, contextfree 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. PrerequisitesPost Conditions The student is able to describethe basic computational models FAs, PDAs, grammars and Turing machines.
 The student is able to formally model a given computational problem and prove its correctness.
 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 Instructor  Walkin or prior appointment by email
 Tanmay Garg
 Monday 23pm MTech lab
 Aashay Mittal
 Monday 1011pm (night) Boys hostel common room
 Anant Jain
 Wednesday 5:306:30pm Boys hostel common room
 Dheeraj Singh
 Thursday 1:302:30 MTech lab
 Manpreet Kaur
 Thursday 67pm MTech lab
 Shanu  Friday 1:302:30pm MTech lab

