Week 3: 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
- Formal Languages
- Finite Automata
- Regular Expressions
- Minimisation of Deterministic Finite Automata
- Context-Free Languages
- Context-Free Grammars and Languages
- Context-Free vs. Regular Languages
- Decidability Problems of Context-Free Languages
- Closure Properties of Context-Free Languages
- Pushdown Automata
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.
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.
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]