Foundations of Informatics Bridging Course

Week 3: Formal Languages and Processes

This page collects the relevant material of the third week of the Foundations of Informatics Bridging Course in Winter Semester 2021/22. It is held from March 7 to 11, 2022, as an online course, and covers the following topics:

  • Part A: Regular Languages
    • Introduction to Formal Languages
    • Deterministic and Nondeterministic Finite Automata
    • Regular Expressions and Languages
    • Closure and Decidability Properties
  • Part C: Context-Free Languages
    • Context-Free Grammars and Languages
    • Relation to Regular Languages
    • Pushdown Automata
    • Closure and Decidability Properties

The planned schedule is as follows (details to follow):

  • Monday, March 7:
    • 09:00-09:30: Kick-off meeting
    • Slides of kick-off
    • Remainder of day: Self-paced learning by means of videos
      • A1: Introduction to Formal Languages
      • A2: Deterministic Finite Automata
      • A3: Operations on Languages and Automata
      • A4: Nondeterministic Finite Automata
      • A5: Powerset Construction
  • Tuesday, March 8:
    • 09:00-10:30: Questions & exercises
    • Exercises
    • Remainder of day: Self-paced learning by means of videos
      • A6: Elimination of epsilon-Transitions
      • A7: Decision Problems for Finite Automata
      • A8: Regular Expressions
      • A9: Regular Languages and Finite Automata
      • A10: Minimisation of Deterministic Finite Automata
  • Wednesday, March 9:
    • 09:00-10:30: Questions & exercises
    • Exercises
    • Remainder of day: Self-paced learning by means of videos
      • C1: Introduction to Context-Free Grammars and Languages
      • C2: Context-Free vs. Regular Languages
      • C3: Chomsky Normal Form
      • C4: The Word Problem for Context-Free Languages
  • Thursday, March 10:
    • 09:00-10:30: Questions & exercises
    • Exercises
    • Remainder of day: Self-paced learning by means of videos
      • C5: The Emptiness Problem for Context-Free Languages
      • C6: Closure Properties of Context-Free Languages
      • C7: Pushdown Automata
      • C8: Pushdown Automata and Context-Free Languages
  • Friday, March 11:
    • 09:00-11:00: Questions, exercises & closing
    • Exercises

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 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.
  • 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. 

Additional Material

The video lessons are based on the following slides (TBA):

  • Regular Languages
  • 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]