Theory of Computing II: Contextfree Languages and PDAs
Was können Sie 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.
Gliederung
- Organization
- Grammars
- Chomsky-Hierarchy
- Elimination of Epsilon Productions
- Closure Properties of Contextfree Languages
- Pumping Lemma for Contextfree Languages
- Intersection and Complement
- Pushdown Automata
- Pushdown Automata and Contextfree Languages
Autoren*innen
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.