Eine formale Sprache ist eine i.a. unendliche Menge von Wörtern über einem vorgegebenen Alphabet. Solche Wörter stellen etwa den Text eines Programms dar oder die Folge der Aktionen einer Berechnung. Die Sprachen, für die wir uns insbesondere interessieren, zeichnen sich dadurch aus, daß sie eine endliche Beschreibung besitzen. Mögliche Beschreibungen sind etwa Grammatiken, d.h. Regelsysteme, die festlegen, wie sich alle Wörter einer Sprache (und nur diese) generieren lassen. Andererseits möchten wir aber auch für ein gegebenes Wort feststellen können, ob es in einer bestimmten Sprache enthalten ist. Für diesen Zweck stellt die Theorie geeignete Automatenkonstruktionen bereit.
Die Vorlesung gehört zum Kanon der Grundvorlesungen.
Die aktive Teilnahme an der angebotenen zweistündigen Übung
wird dringend empfohlen (Scheinerwerb!).
Literatur: