Foundations of Informatics – Formal Languages and Processes
This page covers the third week of the Foundations of Informatics Bridging Course in Winter Semester 2017/18, held in Spring 2018 at b-it, Bonn.
Contents
The following topics are covered:
- Regular Languages
- Formal Languages
- Finite Automata
- Regular Expressions
- Minimization of Deterministic Finite Automata
- Context-Free Languages
- Context-Free Grammars and Languages
- Context-Free and Regular Languages
- Decidability Problems of Context-Free Languages
- Closure Properties of Context-Free Languages
- Pushdown Automata
Objectives
After passing this part of the course, participants are expected to have acquired the following skills:
- Regular Languages:
- to give the basic definitions of finite automata and regular expressions;
- to construct a finite automaton or a regular expression from a given language specification;
- to translate a regular expression into an equivalent finite automaton;
- to compute the set of reachable states of a finite automaton with respect to a given input word;
- to remove ε-transitions from a finite automaton;
- to apply the powerset construction to turn a nondeterministic finite automaton into a deterministic one; and
- to minimize a given deterministic finite automaton.
- Context-Free Languages
- to give the basic definitions of context-free grammars and pushdown automata;
- to construct a context-free grammar or a pushdown automaton from a given language specification;
- to turn a given context-free grammar into Chomsky normal form;
- to apply the CYK algorithm to decide the word problem for a context-free grammar;
- to apply the marking algorithm to decide the emptiness problem for a context-free grammar; and
- to translate a context-free grammar into an equivalent pushdown automaton.
Material
The presentation of the contents is mainly based on the following slides. Sometimes the board is used to develop an example or a formal proof.
- Regular languages: slides, annotated slides, exercises, annotated execises
- Context-free languages: slides, annotated slides, exercises, annotated exercises
Moreover, the following textbooks provide additional information.
- J.E. Hopcroft, R. Motwani, J.D. Ullmann: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001
- A. Asteroth, C. Baier: Theoretische Informatik, Pearson Studium, 2002 [in German]