Übung zur Automatentheorie im Wintersemester 2011/2012

Ergebnisse

Klausur Automatentheorie WS2011/2012
MatrikelnummerBonus(%)Gesamtpunkte(%)Note
180646314564,0
180834222981,0
181232622981,0
2137259221041,0
215011014653,3
278123112752,3
961195910325,0

Termine

Vorlesung

Übung

Klausur

Übungsblätter

In der Regel gibt es für jedes Übungsblatt eine Woche Arbeitszeit. Die Antworten zur Aufgaben sollen begründet werden.

Abgabetermin der H-Aufgaben: bis 15 Uhr dienstags an meine E-Mail-Adresse oder am Anfang der Vorlesung.

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

  1. Beispiele für Automaten und Sprachen (PDF), Abgabe bis 18. Oktober.
  2. Reguläre Ausdrücke und Pumping-Lemma (PDF), Abgabe bis 25. Oktober.
  3. Automaten bauen und erste Monoiden (PDF), Abgabe bis 1. November.
  4. Monoide und Sprachen (PDF), Abgabe bis 8. November.
  5. Minimalautomaten und syntaktische Monoiden (PDF), Abgabe bis 15. November.
  6. Sternfreie Sprachen und aperiodische Monoiden (PDF), Abgabe bis 22. November.
  7. Automaten und Logik (PDF), Abgabe bis 29. November.
  8. Sprachen und Logik (PDF), Abgabe bis 6. Dezember.
  9. Potenzreihe und diskrete Systeme (PDF), Abgabe bis 3. Januar.
  10. Darstellung von diskreten Systemen (PDF), Abgabe bis 10. Januar.
  11. Rationale Ausdrücke für gewichteten Automaten (PDF), Abgabe bis 17. Januar.
  12. Potenzreihen darstellen (PDF), Abgabe bis 24. Januar.
  13. Buchstaben zählen (PDF), Abgabe bis 31. Januar.

Klausur

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

Hinweise

Reguläre Ausdrücke

Zum Zweck der Übung sind reguläre Ausdrücke rationale Ausdrücke. In Programmiersprachen üblichen Notationen und Abkürzungen können verwendet werden:

Bausteine der regulären Ausdrücke in absteigender Priorität
aDie Sprache {a} (ähnlich für andere Buchstaben)
E*Der Stern von E
E+= E · E*
E1·E2Das Produkt von E1 und E2
E1 | E2= E1 ∪ E2

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

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

In Programmiersprachen wird häufig E? für E ∪ {ε} = E ∪ ∅* verwendet, und hat die gleiche Priorität wie *. Die Ausdrücke E*? und E+? haben meistens spezielle Bedeutungen.


Gábor Braun
Johannisgasse 62, Zi 4-39
Tel: (0)341-97-32202
gabor DOT braun AT informatik DOT uni-leipzig DOT de