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. Three meetings days are scheduled:

  • A kick-off meeting on Monday, March 2nd, starting 10:00 at b-it Bonn in room 0.109,
  • one lecture/exercise meeting on Wednesday, March 4th, also 10:00 at b-it Bonn in room 0.109, and
  • another lecture/exercise meeting on Thursday, March 5th, 11:00 at RWTH Aachen University in the seminar room of i2 (building E1, 2nd floor, room 4201b).

On Tuesday, students are expected to to reading work based on the lecture material for Regular Languages, dealing with regular expressions and minimisation of deterministic finite automata.

Contents

The following topics are covered:

  • Regular Languages
    1. Formal Languages
    2. Finite Automata
    3. Regular Expressions
    4. Minimisation of Deterministic Finite Automata
  • Context-Free Languages
    1. Context-Free Grammars and Languages
    2. Context-Free vs. 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
  2. Context-Free Languages

The following exam questions provide an orientation regarding the contents of the exam:

In addition, you may want to have a look at the Theory of Computation online course, in particular the following parts:

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]