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

Lecture

Tuesday Thursday 2:30-4am (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)