| Kommentar: |
*Zusätzlich zur Vorlesung Automaten und formale Sprachen, ist der Besuch einer Übung verpflichtend (Wahlalternativen):
ÜB1: Mo, 10:00-12:00 Uhr, LF035
ÜB2: Di, 08:00-10:00 Uhr, LE 120
ÜB3: Di, 14:00-16:00 Uhr, LK 052
ÜB4: Di, 16:00-18:00 Uhr, LE 103
ÜB5: Mi, 10:00-12:00 Uhr, LB 117
ÜB6: Fr, 10:00-12:00 Uhr, LC 137
Inhalte:
Die Theorie der formalen Sprachen bildet die Grundlage für viele andere Gebiete der Informatik, beispielsweise für Informationsverarbeitung, Compilerbau, Verifikation, Modellierung. Im Rahmen dieser Veranstaltung werden die Grundlagen der formalen Sprachen vermittelt und Fertigkeiten im Umgang mit Automaten und Grammatiken eingeübt. Außerdem soll vermittelt werden, in welchen Bereichen diese Theorie zur Anwendung kommt. Inhalte im Einzelnen: - Grammatiken, Chomsky- Hierarchie - Wortproblem, Syntaxbäume - Reguläre Sprachen (Endliche Automaten, Reguläre Ausdrücke, Pumping-Lemma, Äquivalenzrelationen und Minimalautomaten, Abschlusseigenschaften, Endscheidbarkeit, Anwendung bei Verifikation eines Protokolls zum wechselseitigen Ausschluss) - Kontextfreie Sprachen (Normalformen, Pumping-Lemma, CYK-Algorithmus, Kellerautomaten, deterministisch kontextfreie Sprachen, Abschlusseigenschaften, Entscheidbarkeit, Anwendung bei XML und DTDs) - Kontextsensitive und Typ-0-Sprachen, Turing-Maschinen.
Lernziele:
Die Studierenden sollen Kenntnisse auf dem Gebiet Automaten und formale Sprachen erwerben. Sie sollen sowohl reguläre, als auch kontextfreie Sprachen und die dazugehörigen Automatenmodelle (endliche Automaten,
Kellerautomaten) kennenlernen. Sie sollen selbst in der Lage sein, Automaten und Grammatiken aufzustellen und über ihre Adäquatheit zu argumentieren. Ferner sollen Sie die entsprechenden Algorithmen (Minimierung, CYK, etc.) und Beweismethoden (Pumping-Lemma, etc.) verstehen und anwenden können. Außerdem sollten sie Kenntnisse über Turing-Maschinen und die Grundlagen der Berechenbarkeitstheorie erwerben. Insgesamt sollen sie in die Lage versetzt werden, mit formalen Konzepten umzugehen, selbst formal korrekte Notationen zu verwenden und kleinere Beweise zu führen. |
