## 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 2023/24. It is offered in March 11-15, 2024 as an online course, and covers the following topics:

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

### Schedule

• Monday, March 11:
• 09:00-09:30: Kick-off meeting via Zoom
• Slides of kick-off (TBA)
• Remainder of day: Self-paced learning by means of videos
• Tuesday, March 7:
• 09:00-10:30: Questions & exercises via Zoom
• Exercises (TBA)
• Remainder of day: Self-paced learning by means of videos
• Wednesday, March 8:
• 09:00-10:30: Questions & exercises via Zoom (TBA)
• Exercises (TBA)
• Remainder of day: Self-paced learning by means of videos
• Thursday, March 9:
• 09:00-10:30: Questions & exercises via Zoom
• Exercises (TBA)
• Remainder of day: Self-paced learning by means of videos
• Friday, March 10:
• 09:00-11:00: Questions, exercises & closing via Zoom
• Exercises (TBA)

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