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)
