Übung zur Automatentheorie im Wintersemester 2012/13

Übungsblätter

In der Regel gibt es für jedes Übungsblatt eine Woche Arbeitszeit. Die Antworten zur Aufgaben sollen begründet werden. Sie sollen auf Anförderung Ihre Lösungen vorstellen.

Abgabe der H-Aufgaben: im Postfach „Übungsaufgaben Automatentheorie“ in A 514 bis zum Dienstag 13 Uhr vor der Übung oder an meine E-Mail-Adresse bis zu diesem Zeitpunkt.

Bitte vorbereiten Sie auch die S-Aufgaben für die Übung!

1. Erste Beispiele für Automaten (PDF), Abgabe bis 15. Oktober.
2. Automaten und rationale Ausdrücke (PDF), Abgabe bis 23. Oktober.
3. Pumping Lemma (PDF), Abgabe bis 6. November.
4. Automaten umbauen (PDF), Abgabe bis 13. November.
5. Syntaktische und aperiodische Monoide (PDF), Abgabe bis 27. November.
6. Sprachen durch logische Formeln (PDF), Abgabe bis 4. Dezember.
7. MSO Sätze und sternfreie Sprachen (PDF), Abgabe bis 11. Dezember.
8. Verhalten von gewichteten Automaten (PDF), Abgabe bis 18. Dezember.
9. Darstellung von gewichteten Automaten (PDF), Abgabe bis 8. Januar.
10. Potenzreihen und gewichtete rationale Ausdrücke (PDF), Abgabe bis 15. Januar.
11. Semiring-Homomorphismen und stabile Semi-Module (PDF), Abgabe bis 22. Januar.
12. Rang und zustandsminimale Automaten (PDF), Abgabe bis 29. Januar.

Literatur

1. Handbook of theoretical computer science, Elsevier Science Publishers, B.V., Amsterdam; MIT Press, Cambridge, MA, B 1990 xiv+1273 Ed. Jan van Leeuwen

   Satz von Kleene, Sternhöhe:	Kapitel 1

2. Handbook of weighted automata, Springer-Verlag, Berlin, 2009 xviii+608 Ed. Manfred Droste, Werner Kuich and Heiko Vogler

   Automaten über Semiringen:	Kapitel 3, §1
   rationale und erkennbare Reihen:	Kapitel 4

3. Bakhadyr Khoussainov and Anil Nerode, Automata theory and its applications, Birkhäuser Boston, Inc., Boston, MA, 2001 no. 21, xiv+430

   Satz von Myhill–Nerode:	§2.4
   Satz von Kleene:	§2.5
   MSO Logik:	§2.10

4. Dexter C. Kozen, Automata and computability, Springer-Verlag, New York, 1997 xiv+400

   Minimalisierung von Automaten:	§13–14
   Satz von Myhill–Nerode:	§15–16

5. Jacques Sakarovitch, Elements of automata theory, Cambridge University Press, Cambridge, 2009 xxiv+758

   Monoidautomaten:	Kapitel II

Hinweise