185.086
AUTOMATEN UND FORMALE SPRACHEN

Vorlesung, 2 st.
Rudolf Freund

Freitag, 12.15 - 15.00, Informatiker-Hörsaal.

Inhalt

Die Typen von erzeugenden Grammatiken für die Sprachfamilien der Chomsky-Hierarchie der Formalen Sprachen sowie die entsprechenden Typen analysierender Automaten werden formal definiert und anhand von Beispielen näher erläutert. Die Äquivalenz der korrespondierenden Grammatik- bzw. Automatentypen wird gezeigt. Die Abschlusseigenschaften verschiedener Sprachfamilien gegenüber bestimmten Sprachoperationen werden untersucht. Die Bedeutung regulärer Sprachen für Editoren wird ebenso erläutert wie die Syntaxanalyse über bestimmte Formen kontextfreier Grammatiken. Das Halteproblem für Turingmaschinen und verwandte unentscheidbare Probleme werden erklärt und abschliessend neuere Forschungstrends skizziert.

Lehrziele

In der Vorlesung sollen grundlegende Begriffe aus der Theorie der Formalen Sprachen sowie wichtige mathematische Beweistechniken der Theoretischen Informatik (Induktion, indirekter Beweis, Diagonalisierung) vermittelt und deren Bedeutung für bestimmte Anwendungsgebiete in der Informatik (Syntaxanalyse, Programmverifikation) erläutert werden.

Prüfungen

Der für die Prüfung benötigte Stoff ist in dem für Vorlesung und Übung gemeinsamen Skriptum enthalten. Bei den (schriftlichen) Prüfungen sind keine Unterlagen erlaubt.

Beurteilung

Bei den schriftlichen Vorlesungsprüfungen können maximal 200 Punkte erreicht werden. Die Dauer der Prüfung beträgt 100 Minuten. Die Note ergibt sich dabei nach folgendem Schema:

0 - 100 Punkte: Nicht genügend
101 - 120 Punkte: Genügend
121 - 140 Punkte: Befriedigend
141 - 160 Punkte: Gut
161 - 200 Punkte: Sehr gut

Prüfungstermine

Die Prüfungstermine sowie andere aktuelle Informationen entnehmen Sie bitte der Seite "Aktuell".

Skriptum

Das Skriptum zu Vorlesung und Übung ist am Beginn der ersten Vorlesung im Informatiker-Hörsaal und danach im Sekretariat der Arbeitsgruppe für Anwendungen der Formalen Logik des Institutes für Computersprachen jeweils in den Institutsstunden erhältlich.