Advanced Formal Language Theory, Spring 2026
ETH Zürich: Course catalog
Course Description
This course explores the connection between automata and formal logic. The lectures cover the algebraic characterization of the regular languages definable in many different logical theories, the complexity theory of boolean circuits, and the connection between the two. The interest in these topics has been recently rekindled due to their application in modern-day natural language processing. Both formal logic and circuit complexity are being used extensively to study the expressivity of transformers.
The emphasis is on rigor and depth rather than broad coverage. Students should expect a healthy dose of proof-writing and, thus, mathematical maturity is expected. In terms of background, the class will draw on techniques from discrete math, formal logic, automata theory and abstract algebra. While there are no hard prerequisites, having taken a class that covers these topics would be helpful.
The course is structured around the book Finite Automata, Formal Logic, and Circuit Complexity and the lectures are meant to guide you through the most important bits. In addition to this, you might find it useful to go over the lecture notes from the previous version of the course. The homework exercises, which comprise 100% of the grade, will require you to apply or extend the theory taught in class. The homework will be released throughout the semester in assignments with 3–4 questions each.
News
12.2. Class website is online!
Syllabus and Schedule
On the Use of Class Time
Lectures
There are two slots for AFLT each week: Wednesdays 12:15-14:00 (CAB G 51) and Thursdays 12:15-14:00 (ML F 39). The Wednesday slot will be used for the main lecture, where we will generally cover new material. The Thursday slot may occasionally be used for additional material or to recap concepts. By default, only the Wednesday lecture takes place; we will announce in advance if there will be a session (or any changes) on Thursday. The lecture and the exercise session will generally be given in person and live broadcast on Zoom.
Lectures and exercise sessions will be recorded—link to the Zoom recordings will be posted on the course Moodle page.
We will also publish our class notes. The following syllabus is tentative.
Syllabus
| Date | Topic | Reading | Materials |
|---|---|---|---|
| 18. 2. 2025 | No lecture | ||
| 25. 2. 2025 | Course Logistics | ||
| 25. 2. 2025 | Preliminaries, Automata, Regular Languages | Sections I.1, I.2 | |
| 04. 3. 2025 | Formal Logic and Regular Languages | Chapter II, Chapter III | |
| 11. 3. 2025 | Regular Languages and Finite-state Automata | ||
| 18. 3. 2025 | Model-theoretic Games, FO[<] and FO[+1], The Syntactic Monoid | Chapter IV, Chapter V | |
| 25. 3. 2025 | First-Order Logic | Sections VI.1, VI.2 | |
| 1. 4. 2025 | The Hierarchy in FO | Sections VI.3, VI.4 | |
| 8. 4. 2025 | No class (Easter break) | ||
| 15. 4. 2025 | TBD | ||
| 22. 4. 2025 | TBD | ||
| 29. 4. 2025 | TBD | ||
| 6. 5. 2025 | TBD | ||
| 13. 5. 2025 | TBD | ||
| 20. 5. 2025 | TBD | ||
| 27. 5. 2025 | TBD |
Organisation
Forum
In addition to class time, we will host a forum on Moodle where you can ask questions about assignments and the course content.
Important: There are a few important points you should keep in mind:
- Make sure to follow our announcements on Moodle.
- Tag your questions as described in this document.
- Search for answers in the appropriate channels before posting a new question.
- Ask questions on public channels as much as possible.
Use the Content Questions channel for questions about the content of the course. The Assignment channels are for discussing and asking questions about the respective assignments.
Grading
There will be no final exam for this course. Instead, we will release 5 assignments throughout the semester. You can cooperate on and discuss the assignments with your peers, but you must write up the solutions yourself and disclose your collaborators.
Important: The deadlines for the assignment submissions are:
- Assignment 1: 15.05, 23:59h
- Assignment 2 & 3: 01.07, 23:59h
- Assignment 4 & 5: 01.08, 23:59h
The submissions will be done through the course Moodle page.
We will not extend deadlines. We are counting on you to be organised and submit the work in time.
We require the solutions to be properly typeset.
We recommend using LaTeX (with Overleaf), but markdown files with MathJax for the mathematical expressions are also fine.
Assignments
Below you can find the assignment instructions.
Assignment instructions:
- to be released.
Contact
You can ask questions on the course chat server. Please post all content-related questions there, so others can see them and join the discussion. If you have questions which are not related to the course material and are not of general interest, please contact Irene with Ryan cc-ed.
