Automatentheorie und Formale Sprachen
» Diese Veranstaltung wird auf deutsch gehalten.
Vorlesung im Sommersemester 2002
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| V3 | Di 11:45 - 13:15 Fo2 Fr 10:00 - 10:45 Gr |
16.04.2002 | Thomas, Löding, Rohde |
Inhalt
Automaten und Grammatiken sind Standardwerkzeuge des Informatikers zur Modellierung und Transformation von Systemen und Prozessen. Außerdem bilden sie die Basis für die Definition und Übersetzung von Programmiersprachen, ebenso wie für die Algorithmik über Zeichenreihen (Pattern-Matching).
Im Zentrum dieser Grundvorlesung steht zunächst das Modell des endlichen Automaten, dessen Verhaltensbeschreibung durch reguläre Ausdrücke und die Frage, welche Informatik-Systeme man auf diese Weise modellieren kann. Im zweiten Teil der Vorlesung geht es um die Spezifikation von Daten durch Grammatiken, ihre Erkennung durch Kellerautomaten und die Verbindung mit Formalismen wie XML. Es werden vor allem algorithmische Fragen untersucht, zum Beispiel, ob die Äquivalenz zwischen Automaten bzw. Grammatiken entscheidbar ist (und wenn ja, mit welcher Effizienz).
Themenübersicht:
- Endliche Automaten
- Reguläre Ausdrücke
- Minimierung von Automaten
- Sequentielle Übersetzer
- Grammatiken und ihre Normalformen
- Kontextfreie Sprachen
- Kellerautomaten
- Entscheidbarkeit und Unendscheidbarkeit von Äquivalenzproblemen
Aufzeichnung
Die Vorlesung wird mit einem Screen Recording Tool aufgezeichnet, anschließend multimedial aufbereitet und sowohl hier auf diesen Seiten als auch später auf CD-ROM zur Verfügung gestellt.
Der Kurs wird ebenfalls als virtuelle Lehrveranstaltung im virtuellen Studienplatz von ULI angeboten.
Voraussetzungen:
Grundkenntnisse der Informatik und Mathematik, wie sie in den ersten beiden Semestern des Informatikstudiums ermittelt werden, sind für die Teilnahme erforderlich.Studienrelevanz:
Der durch das erfolgreiche Bestehen der Klausur erworbene Schein wird an der RWTH Aachen als Studienleistung anerkannt.Credit Points:
6 ECTS