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)