Übung zur Automatentheorie im Wintersemester 2012/13

Termine

Vorlesung

Übung

Ü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.

Prüfung

Zur Prüfung zugelassen sind alle, die 50% der H-Aufgaben richtig lösen. Besseres Ergebnis sowie aktive Teilnahme werden positiv bewertet.

Literatur

  1. Handbook of theoretical computer science, Elsevier Science Publishers, B.V., Amsterdam; MIT Press, Cambridge, MA, B xiv+1273 Ed. Jan van Leeuwen
    Satz von Kleene, Sternhöhe:Kapitel 1
  2. Handbook of weighted automata, Springer-Verlag, Berlin, 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, 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, xiv+400
    Minimalisierung von Automaten:§13–14
    Satz von Myhill–Nerode:§15–16
  5. Jacques Sakarovitch, Elements of automata theory, Cambridge University Press, Cambridge, xxiv+758
    Monoidautomaten:Kapitel II

Hinweise

Beispiele für Automaten

Rationale Ausdrücke

Rationale Ausdrücke entsprechen die reguläre Ausdrücke der Programmiersprachen, deshalb können in Programmiersprachen üblichen Notationen und Abkürzungen verwendet werden:

Bausteine der rationalen Ausdrücke in absteigender Priorität
NotationBedeutung
a{a} (ähnlich für andere Buchstaben)
E*n=0En
E+E · E*
E?E ∪ {ε} = E ∪ ∅*
E1·E2Das Produkt von E1 und E2
E1| E2E1∪ E2

Klammern können benutzt werden um den Präzedenz zu überschreiben. Folgendes Beispiel soll den Priorität klar machen:

E1E2*| E3= (E1(E2*)) | E3

Die Operatoren *, ?, + haben die gleiche Priorität. In Programmiersprachen haben die Ausdrücke E*? und E+? meistens spezielle Bedeutungen.


Gábor Braun
Neues Augusteum, A 426
Tel: (0)341-97-32202
gabor DOT braun AT informatik DOT uni-leipzig DOT de