Formal Languages – Theoretical Computer Science

Course Details

Lecturer: Prof. Dr. Arne Meier

Frequency: Every two years (odd-numbered years) in the summer semester

Course type: Vorlesung und Übung (2V + 1Ü + 2S, 7 ECTS)

Examination: Oral exam
Course Contents
This course provides in-depth knowledge about formal languages. Students analyze phenomena from the theory of formal languages beyond the content of basic lectures. They construct various automata and grammar models for regular and context-free languages. They evaluate common transformations and other procedures for these models. They assess the possibilities for applications in syntax analysis. They understand relevant decidability results and are able to apply them to related problems.

Content:

Regular and context-free languages play an extremely important role in compiler construction and other computer science disciplines. The lecture focuses primarily on these two language classes and examines their properties.

Outline:

Finite automata

Myhill-Nerode theorem

Minimal automata

Automata and semigroups

Chomsky normal form and CYK algorithm

Greibach normal form and pushdown automata

Deterministic context-free languages

Decidability questions

Context-sensitive languages and Type-0 languages
Information about exam

The final examination of the module is an oral exam.

Schedule

The exam dates are assigned via an internal institute website (see link below). Note: This does not replace registration for the exam in QIS.

Registration

Depending on your examination regulations, registration in QIS may be required (see link below).

Coursework Requirement

If your examination regulations require coursework for this module, please contact the lecturer.

Materials

Lecture recordings are available for this course.

To the recordings

Further materials can be found in Stud.IP.

To the Stud.IP