Übungen zu Automaten und Formalen Sprachen

Zum nächstenSemester

• Simulationen, die den Grundkurs Theoretische Informatik begleiten und auflockern. Stellen Sie sich auch selbst mal die Frage, ob und wann und wie Ihnen die Benutzung solcher Programme in den vergangenen Semestern geholfen hat oder hätte.

• Eine Anschauung von einem Begriff (einem Maschinenmodell, usw.) bekommt man ja nicht, indem man sich das Ding (den Simulator) nur lange genug anschaut. Es hilft viel, wenn man selbst etwas tut, und Spaß dabei hat. In diesem Sinne richte ich einen Theorie-Spielplatz ein. Das illustriert vor allem Themen aus Berechenbarkeit und Komplexität, paßt also wir angegossen für das vierte Semester. Probieren Sie beispielsweise das PCP-Puzzle, programmiert von Heiko Stamer, und schreiben Sie dann zu den anderen Spielen virtuelle Versionen.

• Wenn Sie absolut und überhaupt gar keine Theorie machen wollen, dann schreiben Sie doch mal ein Programm, das gut CONNECT spielt (Spielregeln). Wenn sich genug Programme finden, können wir gegen Ende des Sommersemesters einen Wettbewerb veranstalten. (Natürlich werden Sie doch Theorie benötigen - Graphentheorie.)

Aktuelles

Die Testate können Sie ab dem 19. Februar abholen.

Es ist kein Wiederholungs-- oder Zusatz--Testat vorgesehen. Sie erhalten jedoch die Möglichkeit, fehlende Punkte aus diesem Semester durch bessere Leistungen im nächsten Semester (Berechenbarkeit und Komplexität) auszugleichen. ("Überschüssige" Punkte aus dem jetzigen Semester sind jedoch nicht auf das folgende übertragbar.)

• (hier steht, was früher mal aktuell war)
• Antworten auf einige gefragte Fragen
• Automatische Korrektur von Übungsaufgaben

Koordinaten

• Vorlesung (Prof. Dr. S. Gerber)
  • freitags 13:15 - 14:45 Hörsaal
• Übungen (Dr. J. Waldmann)
  • mittwochs 13:15 - 14:45 Raum 3-03 (A- und B-Woche)
  • donnerstags 11:15 - 12:45 Raum 3-07 (A- und B-Woche)

• Blatt 1 (zum 25. 10.)
• Blatt 1b (zum 1. 11.)
• Blatt 1b (Aufgabe 4 zum 8. 11.)
• Blatt 2 (Aufgaben 1 und 2 zum 15. 11.)
• Blatt 3 (Aufgaben 1 und 2 zum 29. 11.) (autotool kann Aufgabe31a, Aufgabe31b, Aufgabe31c, Aufgabe32 korrigieren)
• Blatt 3 (Aufgaben 3 und 4 zum 6. 12.) (autotool kann Aufgabe33a, Aufgabe33b, Aufgabe34 (d. h. Teil b) korrigieren)
• Blatt 4 (zunächst ohne 3 und 7) (autotool kann Aufgabe42a, Aufgabe42b, Aufgabe42c, Aufgabe44a, Aufgabe44b, Aufgabe44c, Aufgabe44d korrigieren)
• zum 10. 1.:
  • Blatt 4:
    • Aufgabe 3 (Korrektur mit autotool, siehe Hinweise)
    • Aufgabe 4 (entweder kontextfreie Grammatik angeben und mit autotool prüfen oder mit Pumping-Lemma beweisen, daß es keine gibt.)
  • Blatt 4b: Aufgabe 10
• zum 17. 1.: Blatt 5 (autotool kann Aufgabe56, 57a, 57b korrigieren)
• zum 24. 1.: Blatt 9 (zwei Seiten!) (autotool kann Aufgabe93 korrigieren)

  Wer noch Turingmaschinen über möchte: autotool kann auch Aufgaben 7a, 7b von Blatt 4

Skript

Ergänzendes Material

• Anwendungen der Automatentheorie in Standardsoftware:
  • Haben Sie schonmal ein File mit gcc kompiliert? Dann wurde es von einem deterministischen Kellerautomaten gelesen.
  • Haben Sie schonmal mit grep nach einer Zeichenkette gesucht? Dann wurde extra für Sie ein endlicher Automat gebaut.
  Unter dem Motto RTFC (Read the F... Code) lenken wir Ihre Aufmerksamkeit eindringlichst auf diese Quelltexte.

• Skripte und Übungsaufgaben zu früheren Vorlesungen:
  • (Prof. Gerber, 1998)
  • (Prof. Herre, 199?)