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!
Zur Prüfung zugelassen sind alle, die 50% der H-Aufgaben richtig lösen. Besseres Ergebnis sowie aktive Teilnahme werden positiv bewertet.
Satz von Kleene, Sternhöhe: | Kapitel 1 |
---|
Automaten über Semiringen: | Kapitel 3, §1 |
---|---|
rationale und erkennbare Reihen: | Kapitel 4 |
Satz von Myhill–Nerode: | §2.4 |
---|---|
Satz von Kleene: | §2.5 |
MSO Logik: | §2.10 |
Minimalisierung von Automaten: | §13–14 |
---|---|
Satz von Myhill–Nerode: | §15–16 |
Monoidautomaten: | Kapitel II |
---|
Rationale Ausdrücke entsprechen die reguläre Ausdrücke der Programmiersprachen, deshalb können in Programmiersprachen üblichen Notationen und Abkürzungen verwendet werden:
Notation | Bedeutung |
---|---|
a | {a} (ähnlich für andere Buchstaben) |
E* | ⋃n=0∞En |
E+ | E · E* |
E? | E ∪ {ε} = E ∪ ∅* |
E1·E2 | Das 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:
Die Operatoren *, ?, + haben die gleiche Priorität. In Programmiersprachen haben die Ausdrücke E*? und E+? meistens spezielle Bedeutungen.