## 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:

- Exam questions (.zip archive)

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

- Deterministic Finite State Machines: Introduction
- Deterministic Finite State Machines: Examples
- Operations on Regular Languages
- Nondeterministic Finite State Machines: Introduction
- Nondeterministic Finite State Machines: Formal Definition
- Equivalence of Deterministic and Nondeterministic FSMs
- Closure of Regular Operations
- Regular Expressions
- Equivalence of Regular Expressions and Regular Languages
- Context-Free Grammars and Languages
- An Example Context-Free Language and Grammar
- Chomsky Normal Form
- Pushdown Automata

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]