Formale Sprachen u. Automatentheorie

Vorlesung Formale Sprachen und Automaten - FT06


Die Vorlesung Formale Sprachen und Automaten im Herbsttrimester 2006 wird von Prof. Dr. Peter Hertling gehalten und findet zu den folgenden Zeiten statt:

Mo. 10.00 - 12.00 Uhr, Hörsaal 0101
Do. 12.00 - 13.00 Uhr, Hörsaal 2211



Zur Vorlesung wird ein Skript erstellt. Dieses wird jeweils kurz vor oder nach der Vorlesung auf dem Dokumentenserver der Universität der Bundeswehr München bereitgestellt, und zwar hier:

Dokumente zur Vorlesung Formale Sprachen und Automatentheorie
Auf dem Dokumentenserver werden auch die Übungsblätter bereitgestellt.

An dem Skript auf dem Dokumentenserver sind nach dem ersten Ins-Netz-Stellen an den folgenden Tagen die folgenden Korrekturen und Änderungen vorgenommen worden (Korrekturen von Tippfehlern werden im Allgemeinen nicht erwähnt, außer wenn die Gefahr eines Missverständnisses durch den Tippfehler groß ist. Auch Korrekturen von grammatikalischen Fehlern werden nicht erwähnt):
  • 06.10.2006:
    • Abschnitt 1.1, letzter Punkt vor Beispiel 1.1: "Sprache" wurde ersetzt durch "(formale) Sprache".
    • Abschnitt 1.2, Definition 1.4: In Zeile 2 auf Seite 3 musste einmal der griechische Buchstabe Pi durch V ersetzt werden. Beispiel 1.5: in der dritten Zeile fehlte das Wort 011110. Beispiel 1.6: in den Erläuterungen zu der Ableitung des Wortes a^nb^nc^n fehlten schließende Klammern. Am Ende des Korrektheitsnachweises wurde ein Satz ergänzt.
    • Abschnitt 1.3, Beispiel 1.13: In dem Vorspann zu dem Algorithmus für N ist ein Satz anders formuliert worden. Beweis von Satz 1.17: der drittletzte Satz ist geändert worden. Beweis von Satz 1.20: im dritten Schritt musste V durch V' ersetzt werden.
  • 12.10.2006:
    • Abschnitt 1.3, Definition 1.9: Ein Detail in der Definition von kontextsensitiven Grammatiken ist geändert worden.
  • 16.10.2006:
    • Abschnitt 1.4: Im Beweis von Satz 1.22 ist kenntlich gemacht worden, wo die Voraussetzung verwendet wird, dass die Grammatik monoton ist. Außerdem musste in Beispiel 1.23 einmal "w in {a,b,c}" durch "w in {a,b,c}^*" ersetzt werden.
  • 16.10.2006:
    • Abschnitt 2.1, Beispiel 2.3: In der Angabe der Sprache gab es einen Tippfehler.
    • Abschnitt 2.2, Definition 2.10: Hier gab es auch einen Tippfehler.
  • 23.10.2006:
    • Abschnitt 1.1: In der Defintion von L^+ musste L^+ auf der rechten Seite durch L^* ersetzt werden (auch in den Folien korrigiert).
    • Abschnitt 2.1: In Beispiel 2.5 musste einmal "Zustand 0" durch "Zustand q_1" ersetzt werden.
    • Abschnitt 2.3: Im Beweis von Satz 2.22 wurde der Korrektheitsbeweis sauberer formuliert. In Beispiel 2.25 war der Unterschied zwischen deterministischen endlichen Automaten und vollständigen deterministischen endlichen Automaten nicht beachtet worden. Das wurde korrigiert.
  • 31.10.2006:
    • Abschnitt 2.4: Abbildung 10 musste korrigiert werden.
  • 13.11.2006:
    • Abschnitt 2.8: Der zweite Algorithmus für das Äquivalenzproblem ist dank eines Hinweises eines Hörers der Vorlesung vereinfacht worden.
  • 20.11.2006:
    • Abschnitt 3.2: In Beispiel 3.17 enthielt die zuletzt angegebene Regelmenge P' eine Regel zuviel. Der Algorithmus zum ersten Schritt des Beweises von Satz 3.19 enthielt in der "entferne"-Zeile einen Fehler.
  • 27.11.2006:
    • Abschnitt 3, Einleitung: Die Einleitung wurde etwas geändert, da in dem Abschnitt zum Cocke-Younger-Kasami-Algorithmus auch die Entscheidbarkeit anderer Fragen zu kontextfreien Sprachen untersucht wurde.
    • 18.12.2006:
      • Abschnitt 4.2: In Definition 4.6 musste "Ein-Band-Turingmaschine" durch "Turingmaschine" ersetzt werden. In Beispiel 4.8 war die informelle Beschreibung der Schritte 4, 5 und 6 der Turingmaschine etwas missverständlich und wurde geändert.
      • Abschnitt 4.3: Im Beweis der Richtung "=>" von Satz 4.13 musste einmal "linke Komponente" durch "obere Komponente" ersetzt werden. In der Definition der Regeln im gleichen Beweis musste einmal L durch ersetzt werden.
      • Abschnitt 4.4: Die Komplexitätsklasse PSPACE wird über deterministische Turingmaschinen definiert.

Übungen


Die Übungen werden von Frau Dipl.-Inf. Gisela Krommes und Herrn Dr. Christoph Spandl betreut. Termin und Räume:

Do. 10.00 - 12.00 Uhr, Gebäude 36, Raum 01241 und Raum 01242


Letzte Änderung: 18. Dezember 2006