104.458 AKINF: Automata and Formal Languages
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2023S, VO, 2.0h, 3.0EC

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture
  • Format: Presence

Learning outcomes

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.

Subject of 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).

Teaching methods

Lecture

Mode of examination

Oral

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Fri14:15 - 15:4503.03.2023 - 30.06.2023 Dissertantenraum, Freihaus, 8th floor, green arealecture
AKINF: Automata and Formal Languages - Single appointments
DayDateTimeLocationDescription
Fri03.03.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri10.03.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri17.03.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri24.03.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri31.03.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri21.04.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri28.04.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri05.05.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri12.05.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri26.05.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri02.06.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri09.06.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri16.06.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri23.06.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture
Fri30.06.202314:15 - 15:45 Dissertantenraum, Freihaus, 8th floor, green arealecture

Examination modalities

Oral Exam

Course registration

Not necessary

Curricula

Study CodeObligationSemesterPrecon.Info
860 GW Optional Courses - Technical Mathematics Not specified

Literature

Course notes will be made available.

Previous knowledge

Knowledge of the elementary theory of formal languages (as taught in the course 108.036 "Theoretical Computer Science") is helpful.

Accompanying courses

Language

if required in English