After successful completion of the course, students are able to...
The intended learning outcome of this course is to understand the contents of the course. Among other effects, this understanding forms the basis for the capability to correctly reproduce the statements and notions covered in the course as well as for the ability to explain and apply the proof techniques used in the course.
Automata theory is a central subject of theoretical computer science. Finite automata are the simplest possible machines and they appear explicitely as well as implicitely in a variety of different subjects and applications in both computer science and mathematics.
In mathematics, automata and formal languages are firmly tied to monoids and semirings. In this course we will first develop classical automata theory on the basis of continuous semirings. This leads to the more general notion of weighted automaton, as well as to corresponding generalisations of formal languages, grammars, etc. in a natural way. In the second part of the course we will deal with the classification of regular languages by properties of their syntactic monoids. As one of the most important results of this kind we will prove the theorem of Schützenberger (the characterisation of the star-free languages by aperiodic monoids).