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 familiar with the basic computational models FAs, PDAs, grammars and Turing machines.
 The student is able to choose a suitable computational model for a given problem (formal language) and knows how to verify the correctness.
 The student understands the concept of undecidability and recursive enumerability and is able to give examples of respective problems.
 The student has improved his/her abstract thinking skills.
LectureTuesday Thursday 2:304am (C02) 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)
