Theory of Computing: Contextfree Languages and Pushdown Automata (#cofreeLangMOOC)

Zielgruppe: Studierende
Programm: Tech
Autor/in: Andreas Schäfer
Arbeitsaufwand: ≈ 45 Stunden
Kursbeginn: Flexibel
Format: Selbstlernkurs Einschreiben

Was erwartet Dich in diesem Kurs?

Formal Languages and Automata provide the basis for analyzing user input from addresses in web forms to complex Java code. This 3-part course provides the basics of the theory. It also shows the limits of each machine model and finally the limits of computability in general.

This course, building on the previous one, features contextfree languages and pushdown automata.

Was kannst Du in diesem Kurs lernen?

With the help of this course, we want you to achieve the following learning outcomes:

  • You can read and write the formal notation of a grammar and classify grammars with regard to the Chomsky hierarchy.
  • You can eliminate epsilon productions from grammars.
  • You can name operations that contextfree grammars are closed under.
  • You can proof that a language is not contextfree.
  • You can describe the idea and the mode of operation of pushdown automata.
  • You can transfer contextfree grammars into pushdown automata.


  1. Organization
  2. Grammars
  3. Chomsky-Hierarchy
  4. Elimination of Epsilon Productions
  5. Closure Properties of Contextfree Languages
  6. Pumping Lemma for Contextfree Languages
  7. Intersection and Complement
  8. Pushdown Automata
  9. Pushdown Automata and Contextfree Languages


Prof. Dr. Andreas Schäfer

Andreas Schäfer received his PhD 2007 from the Carl von Ossietzky University in Oldenburg, Germany. 

He then worked at the European Patent Office for 5 years. Since 2012 he is Professor of Computer 

Science at the Technische Hochschule Lübeck. His interests include Automata Theory, Logic and Formal Methods. 


In this course, you can earn Badges and Training certificate.