Foundations of Informatics Bridging Course

Foundations of Informatics – Formal Languages and Processes

This page covers the third week of the Foundations of Informatics Bridging Course in Winter Semester 2019/20, held from 2 to 6 March 2019. Currently, two meetings days are scheduled at b-it Bonn in room 0.109:

  • A kick-off meeting on Monday, March 2nd, starting 10:00 and
  • a discussion meeting on Thursday, March 5th, also at 10:00.

The remainder will be organised as an online course. Details will follow soon.

Contents

The following topics are covered:

  • Regular Languages
    1. Formal Languages
    2. Finite Automata
    3. Regular Expressions
    4. Minimization of Deterministic Finite Automata
    5. The Pumping Lemma
  • Context-Free Languages
    1. Context-Free Grammars and Languages
    2. Context-Free and Regular Languages
    3. Decidability Problems of Context-Free Languages
    4. Closure Properties of Context-Free Languages
    5. Pushdown Automata

Objectives

After passing this part of the course, participants are expected to have acquired the following skills:

  1. 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 description;
    • 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 minimise a given deterministic finite automaton
  2. 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 description;
    • 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.

  1. Regular Languages (TBA)
  2. Context-Free Languages (TBA)

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]