Wörter und formale Sprachen sind ein grundlegendes Abstraktionsmittel der Informatik, mit denen z.B. Programme und verschiedene Arten von Datenstrukturen beschrieben werden können. In dieser Vorlesung werden zwei wichtige Klassen von formalen Sprachen vorgestellt, die regulären Sprachen und die kontextfreien Sprachen. Eng verknüpft mit formalen Sprachen sind Automaten und Grammatiken, die endliche Beschreibungen von unendlichen Sprachen zur Verfügung stellen. Wir stellen Automaten und Grammatiken für reguläre und kontextfreie Sprachen vor und studieren zentrale algorithmische Probleme, die im Zusammenhang damit stehen.

Semester: WT 2022/23