News
Exercise sessionsWritten on 23.04.24 by Leon Pernak Dear students, The exercise sessions will be happening on Wednesdays at 16:00 in SR9. The first two sessions will be on May 8th and 15th, the following ones will be eventually added to the timetable here in CMS. Best, Leon |
Algebraic Methods in Formal Language Theory
This lecture explores some algebraic techniques that are used in the study of formal languages, mainly coming from monoid and semigroup theory. There will be a gentle introduction to the algebraic structures (what is a monoid/semigroup, the free monoid, presentations of monoids, Levi's lemma...) and also a discussion of some basic terminology in formal language theory, if necessary (automata, regular language, ...).
Then we will survey the roles algebraic definitions play in formal language theory: We will introduce syntactic and transition monoids and set out to prove Eilenberg's correspondence theorem, which establishes a connection between a regular (sub-) language and the monoids recognizing it. We will spend time discussing various applications of this theorem, by characterizing different subclasses of regular languages via their recognizing monoids.
If time permits, we will also study additional results like some theorems of Schützenberger and Reitermann.
The lecture will be as self-contained as possible, so no previous knowledge is required. However, if it turns out that the attending students already have an extensive background in either basic algebra and/or formal language theory, we might keep the introduction rather short to make the lecture more interesting.
Lecture:
Tuesdays, 10-12am c.t. in
room SR 6 (=2.17) on
2nd floor of building E2.4 (Maths building)
Exercises:
Wednesdays, 16-18 (see timetable for exercise dates)
room SR 9 on
3rd floor of building E2.4