Automatentheorie

Creative-Commons-Lizenz CC BY-NC-SA

Die vorliegenden Materialien wurden von Daniel Hoherz und André Tempel erstellt. Sollten andere Editoren die Materialien erstellt haben, werden diese explizit genannt.

Kennzeichnung der Anforderungsniveaus: Abschnitte mit gA gehören zum grundlegenden, Abschnitte mit eA zum erhöhten Anforderungsniveau. Abschnitte ohne Kennzeichnung bearbeiten alle Kurse.

Wie funktioniert ein „Automat“?

Es ist passiert. Sie waren auf einer längeren Geburtstagsparty, kommen früh morgens nach Hause und stellen erschrocken fest, dass Sie Ihren Schlüssel wohl zuhause vergessen haben!

Durch Klingeln scheint bei Ihnen zuhause niemand mehr wach zu werden. Da fällt Ihnen ein, dass Ihre Eltern kürzlich an Ihrem Garagentor ein smartes Schloss mit Keypad angebracht haben. Jede Person in Ihrer Familie hat eine eigene PIN, mit welcher man das Tor öffnen und schließen kann.

Smartes Schloss mit Keypad am Eingang
Bild von einer KI erstellt

Ob Ihnen Ihre PIN noch einfällt, ist fraglich. Nach einigen erfolglosen Versuchen fragen Sie sich langsam, wie das System hinter dem Keypad eigentlich arbeitet.

Ihr Bearbeitungsfortschritt: 0%
🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Sie haben alle Aufgaben bearbeitet und abgehakt. Vergleichen Sie Ihre Ergebnisse nun mit der Gesamtmusterlösung.

Deterministische endliche Automaten

Auf fachlicher Ebene bezeichnet man das gesamte Szenario mit dem Keypad als deterministischen endlichen Automaten, kurz DEA.

Ein DEA ist ein sogenanntes 5-Tupel (also besteht er aus fünf Komponenten). Das 5-Tupel eines DEA besteht aus \((Q, \Sigma, \delta, s, F)\), wobei die einzelnen Komponenten wie folgt definiert sind:

DefinitionKeypad
\(Q\) \(Q\) ist eine nicht leere, endliche Menge von Zuständen, in denen sich der DEA befinden kann. Bsp. beim Keypad: \(Q = \{q_0, q_1, q_2, q_3, q_4, q_F\}\)
\(\Sigma\) \(\Sigma\) ist ein nicht leeres, endliches Eingabealphabet, also alles, was der Automat als Eingabezeichen erhalten kann. Bsp. Keypad: \(\Sigma = \{0, \dots, 9\}\)
\(\delta\) \(\delta\) ist die Übergangsfunktion, die jeder Kombination aus aktuellem Zustand und einem Eingabezeichen einen Folgezustand zuordnet. Diese Funktion stellt man mathematisch durch \(\delta: Q \times \Sigma \rightarrow Q\) dar. Die Übergangsfunktion kann in Form einer Tabelle angegeben werden. Das bedeutet, dass einem Paar, z. B. \((q_0, 4)\) bei unserem Keypad ein Folgezustand, hier \(q_1\), zugeordnet wird: \((q_0, 4) \rightarrow q_1\).
\(s\) \(s \in Q\) ist der Startzustand, in dem sich der DEA zu Beginn befindet. Achtung: Es ist immer nur ein Startzustand möglich. Bsp. Keypad: \(s = q_0\).
\(F\) \(F \subseteq Q\) ist die Menge der akzeptierenden Zustände, kurz Endzustände.
Achtung, es darf auch mehrere Endzustände geben. Ein Wort wird akzeptiert, wenn sich der DEA nach dem Lesen des ganzen Wortes in einem Endzustand befindet.
Bsp. Keypad: \(F = \{q_4\}\).

Der Zustandsgraph zum Zahlenschloss DEA sieht wie folgt aus:

Zustandsgraph zum Zahlenschloss DEA
Zustandsgraph des Zahlenschloss-Automaten mit Start-, Fehler- und Endzustand
Vollständigkeit: Ein DEA ist immer vollständig: Für jeden Zustand und jedes Zeichen aus \(\Sigma\) gibt es genau einen Übergang. Den Fehlerzustand (hier \(q_F\)) darf man im Zustandsgraphen weglassen, wenn man dazuschreibt, dass alle fehlenden Übergänge in den Fehlerzustand führen.

Aufgaben

Arbeiten Sie die folgenden Aufgabenstellungen Schritt für Schritt durch. Nutzen Sie bei Bedarf die Fortschrittsanzeige, um Ihren Bearbeitungsstand festzuhalten.

Ihr Bearbeitungsfortschritt: 0%
Aufgabe 1: Schlosssystem am Rüsselsspringergehege (Einzel- oder Partnerarbeit)

Der Kontext und die grundlegende Idee der Aufgabe wurde von Lukas Köhl (Osnabrück, 2023) entworfen.

Im Osnabrücker Zoo hat die Direktorin ein modernes Schloss am Rüsselsspringergehege angebracht. Dieser Schritt wurde notwendig, da auch nicht berechtigte Mitarbeitende ständig die Rüsselsspringer streicheln wollten. Das Schloss wird über ein Keypad bedient.

Rüsselsspringer im Zoo Osnabrück
Abb.: Kurzohr-Rüsselsspringer im Gehege

Zunächst bekommen drei Mitarbeitende Zugang zum Gehege. Die drei Personen haben als PINs 1059, 3064 und 0159 erhalten. Das Schloss wartet, bis vier Ziffern eingegeben wurden und prüft anschließend, ob die Eingabe akzeptiert wird.

Entwerfen Sie einen DEA in Form eines Zustandsgraphen, welcher als Akzeptor der erlaubten Eingaben arbeitet. Geben Sie für Ihren DEA auch die formale Darstellung als 5-Tupel an.

Hilfe 1 (Zustände planen):
Jeder Zustand steht für die bisher richtig eingegebenen Ziffern, z. B. „1 gelesen“, „10 gelesen“, „105 gelesen“. Zeichnen Sie zuerst den Pfad für 1059 und ergänzen Sie dann 3064 und 0159.
Hilfe 2 (Gemeinsame Teile):
Nach „10“ und nach „01“ fehlt in beiden Fällen noch „59“. Diese beiden Pfade können deshalb ab der dritten Ziffer zusammenlaufen.
Hilfe 3 (5-Tupel):
Q: alle Zustände einschließlich Fehlerzustand, Σ = {0, …, 9}, δ als Tabelle („–“ für Übergänge in den Fehlerzustand), s und F.

Damit auch bei anderen Tiergehegen der Zugang digital geregelt werden kann, sollen nun überall die neuen Schlösser mit Keypad angebracht werden. Die berechtigten Mitarbeitenden der Tierpflege können sich nun ihre PIN selbst aussuchen. Aus Sicherheitsgründen wird die Zusammensetzung einer erlaubten PIN verschärft.

Wählen Sie eine der folgenden drei Schwierigkeitsstufen aus:

StandardvarianteSchwierige VarianteSchwere Variante
Eine PIN muss aus mindestens drei und höchstens vier Ziffern bestehen und darf nicht die Ziffernfolge 123 beinhalten. Eine PIN muss aus mindestens drei und höchstens fünf Ziffern bestehen und darf nicht die Ziffernfolge 123 beinhalten. Eine PIN muss aus mindestens vier und höchstens sechs Ziffern bestehen und darf nicht die Ziffernfolge 1234 beinhalten.

Arbeitsauftrag: Geben Sie je zwei strukturell verschiedene akzeptierte und nicht akzeptierte Eingaben an. Entwerfen Sie einen DEA in Form eines Zustandsgraphen, welcher als Akzeptor der erlaubten Eingaben arbeitet.

Hilfe 1 (Was muss sich der DEA merken?):
Zwei Dinge: wie viele Ziffern schon eingegeben wurden und wie weit die verbotene Folge schon begonnen hat.
Hilfe 2 (Verbotene Folge verfolgen):
Nach einer 1 ist die Folge 123 „eine Stelle weit“ begonnen, nach 12 zwei Stellen. Folgt dann eine 3, ist die PIN verboten. Folgt eine andere Ziffer, beginnt die Suche von vorn – es sei denn, die neue Ziffer ist selbst eine 1.
Hilfe 3 (Endzustände):
Endzustände sind alle Zustände mit erlaubter Länge, in denen die verbotene Folge nicht vorkam.

Wählen Sie eine der folgenden drei Schwierigkeitsstufen aus:

StandardvarianteSchwierige VarianteSchwere Variante
Eine PIN muss aus mind. 3 und max. 4 Ziffern bestehen. Außerdem darf eine PIN nicht vier gleiche Ziffern beinhalten. Nur die Ziffern 1, 2, 3 oder 4 dürfen eingegeben werden. Eine PIN muss aus mind. 3 und max. 5 Ziffern bestehen. Außerdem darf eine PIN nicht drei gleiche Ziffern hintereinander beinhalten (z. B. 11211 ist erlaubt, 21115 nicht). Eine PIN muss aus mind. 4 und max. 6 Ziffern bestehen. Außerdem darf eine PIN nicht vier aufeinanderfolgende Ziffern in auf- oder absteigender Reihenfolge beinhalten.

Arbeitsauftrag: Geben Sie je zwei strukturell verschiedene akzeptierte und nicht akzeptierte Eingaben an. Entwerfen Sie einen DEA in Form eines Zustandsgraphen, welcher als Akzeptor der erlaubten Eingaben arbeitet.

Hilfe 1 (Was muss sich der DEA merken?):
Die Anzahl der Ziffern und die zuletzt eingegebene Ziffer; je nach Variante auch, wie oft sie gerade hintereinander kam oder ob die letzten Ziffern auf- bzw. absteigend aufeinanderfolgen.
Hilfe 2 (Übersicht behalten):
Der Graph wird schnell groß. Arbeiten Sie mit Kantenbeschriftungen wie „gleiche Ziffer“ und „andere Ziffer“ und zeichnen Sie gleichartige Teile nur einmal ausführlich.

Die Keypads werden verbessert. An einem Keypad können nun Ziffern, Klein- und Großbuchstaben sowie Sonderzeichen eingegeben werden.

Wählen Sie eine der folgenden drei Schwierigkeitsstufen aus:

StandardvarianteSchwierige VarianteSchwere Variante
Ein erlaubtes Passwort muss mindestens aus vier Zeichen und mindestens zwei der vier Zeichenarten bestehen. Ein erlaubtes Passwort muss mindestens aus vier Zeichen und mindestens drei der vier Zeichenarten bestehen. Bearbeiten Sie zuerst die schwierigere Variante. Erläutern Sie, wie sich der DEA ändert, wenn ein sicheres Passwort aus mindestens acht Zeichen und allen Arten von Zeichen zusammengesetzt sein muss.

Arbeitsauftrag: Geben Sie je zwei strukturell verschiedene akzeptierte und nicht akzeptierte Eingaben an. Entwerfen Sie einen DEA in Form eines Zustandsgraphen, welcher als Akzeptor der erlaubten Eingaben arbeitet.

Hilfe 1 (Zeichenarten zusammenfassen):
Beschriften Sie Kanten mit der Zeichenart statt mit einzelnen Zeichen: Z (Ziffer), k (Kleinbuchstabe), G (Großbuchstabe), S (Sonderzeichen).
Hilfe 2 (Was muss sich der DEA merken?):
Welche Zeichenarten schon vorkamen und wie viele Zeichen schon eingegeben wurden. Ab der Mindestlänge ist die genaue Zahl egal.
Hilfe 3 (Zustände):
Ein Zustand ist ein Paar (Länge, Menge der vorgekommenen Zeichenarten). Überlegen Sie, welche Paare überhaupt erreichbar sind.
Aufgabe 2: Artikel-Erkennung (Einzelarbeit)

Endliche Automaten können genutzt werden, um grammatikalische Strukturen oder bestimmte Wörter einer Sprache zu erkennen.

Entwerfen Sie den Zustandsgraphen eines DEA, der die Artikel der, die, das, den, dessen, deren und dem erkennt.

Hilfe 1 (Gemeinsamer Anfang):
Alle Artikel beginnen mit d. Danach verzweigt der Graph: e (der, den, dem, dessen, deren), i (die) und a (das).
Hilfe 2 (Gemeinsame Enden):
Wörter, die vollständig gelesen sind, können in einen gemeinsamen Endzustand führen. Achtung: „der“ ist ein Wort und zugleich der Anfang von „deren“.
Hilfe 3 (Fehlerzustand):
Den Fehlerzustand dürfen Sie weglassen, wenn Sie dazuschreiben, dass alle fehlenden Übergänge dorthin führen.
Aufgabe 3: Eingabealphabete bestimmen (Einzelarbeit)

Entscheiden Sie, welche der folgenden Mengen mögliche Eingabealphabete für endliche Automaten sind:

  1. \(\Sigma = \{1, 3, 5, 7, \dots\}\)
  2. \(\Sigma = \{\}\)
  3. \(\Sigma = \{A, B, 2, 4, +, -\}\)
  4. \(\Sigma = \{\pi, \sqrt{2}, 1\}\)
Hilfe 1 (Bedingungen):
Ein Eingabealphabet muss endlich und nicht leer sein. Prüfen Sie jede Menge auf diese beiden Eigenschaften.
Hilfe 2 (Ungewohnte Zeichen):
Welche Bedeutung ein Zeichen hat, spielt keine Rolle. Auch π oder √2 können einfach Zeichen sein.

Geben Sie ein geeignetes Eingabealphabet zu den folgenden Wörtern an. (Einzelne Wörter werden durch ein Komma getrennt):

  1. a, b, c
  2. AabBabB
  3. bbbb
  4. (a-b)*3
  5. 100011011
  6. IV, I, III, XII
  7. 8124
Hilfe 1 (Vorgehen):
Sammeln Sie alle Zeichen, die in den Wörtern einer Zeile vorkommen. Jedes Zeichen kommt nur einmal in die Menge.
Hilfe 2 (Groß und klein):
a und A sind verschiedene Zeichen. Auch Klammern, Rechenzeichen und das Komma innerhalb eines Wortes zählen mit; das Komma zwischen den Wörtern trennt nur.
Aufgabe 4: Analyse eines vorgegebenen Zustandsgraphen (Einzelarbeit)

Wir betrachten den folgenden Zustandsgraphen eines DEA:

Zustandsgraph zu Aufgabe 4
Abb.: Zustandsgraph mit Zuständen q0, q1, q2, q3

Geben Sie je zwei Wörter an, welche vom DEA akzeptiert bzw. nicht akzeptiert werden.

Hilfe 1 (Wege suchen):
Folgen Sie vom Startzustand aus den Pfeilen, bis Sie in einem Endzustand sind. Die Kantenbeschriftungen ergeben ein akzeptiertes Wort.
Hilfe 2 (Nicht akzeptierte Wörter):
Ein Wort wird nicht akzeptiert, wenn es in einem Zustand endet, der kein Endzustand ist, oder in den Fehlerzustand führt.

Beschreiben Sie möglichst präzise die Sprache, welche vom DEA akzeptiert wird.

Hilfe 1 (Anfang und Ende):
Womit beginnt jedes akzeptierte Wort, womit endet es?
Hilfe 2 (Wiederholungen):
Welche Schleifen gibt es zwischen Endzustand und anderen Zuständen? Notieren Sie die Zeichenfolgen, die man auf diesen Rundwegen liest.

Geben Sie die formale Definition des DEA als 5-Tupel \((Q, \Sigma, \delta, s, F)\) an.

Hilfe 1 (Schema):
Gehen Sie das 5-Tupel der Reihe nach durch: Q, Σ, δ, s, F. Für δ legen Sie eine Tabelle mit einer Zeile je Zustand und einer Spalte je Zeichen an.
Hilfe 2 (Vollständigkeit):
Jede Zelle der Tabelle muss gefüllt sein. Fehlt im Graphen ein Übergang, führt er in den Fehlerzustand.
Aufgabe 5: Modellierung eines BluRay-Players (Einzelarbeit)

Ein einfacher BluRay-Player hat die Funktionen „Ruhe“, „Film läuft“ und „Schneller Vorlauf“ sowie die Tasten „Play“, „Forward“ und „Stop“. Zu Beginn ist der Player in Ruhe. Der Player soll als Akzeptor modelliert werden: Akzeptiert werden genau die Tastenfolgen, nach denen der Film läuft.

Entwerfen Sie ein Modell des Players als DEA in Form eines Zustandsgraphen. Geben Sie je zwei akzeptierte und nicht akzeptierte Tastenfolgen an.

Hilfe 1 (Zustände und Eingaben):
Die drei Funktionen sind die Zustände, die drei Tasten die Eingabezeichen.
Hilfe 2 (Vollständigkeit):
Legen Sie für jeden Zustand und jede Taste fest, was passiert. Bewirkt eine Taste nichts, zeichnen Sie eine Schleife.
Hilfe 3 (Endzustand):
Akzeptiert werden die Tastenfolgen, nach denen der Film läuft. Welcher Zustand ist also Endzustand?
Aufgabe 6: Akzeptierte Sprache aus Graph und 5-Tupel (Partnerarbeit)

Gegeben ist der folgende DEA:

\(Q = \{q_0, q_1, q_2\}\)
\(\Sigma = \{a, b\}\)
\(s = q_0\)
\(F = \{q_0\}\)
Zustandsgraph zu Aufgabe 6

Ermitteln Sie die vom DEA akzeptierte Sprache und erläutern Sie die Bedeutung der einzelnen Zustände.

Hilfe 1 (Kurze Wörter testen):
Probieren Sie die kürzesten Wörter aus: ε, a, b, ab, ba, aa … Welche werden akzeptiert?
Hilfe 2 (Bedeutung der Zustände):
Formulieren Sie für jeden Zustand, was bis dahin gelesen wurde, z. B. „ein a wurde gelesen, es fehlt noch …“. Gibt es einen Zustand, aus dem man nie mehr herauskommt?
Aufgabe 7: Paritätsprüfer für ungerade Anzahl Einsen (Partnerarbeit)

Die Sprache \(L_{\text{ung}}\) mit dem Alphabet \(\{0, 1\}\) besteht aus Wörtern, die nur aus den Ziffern 0 und 1 bestehen. Die Anzahl der Ziffer 1 in jedem Wort muss aber stets ungerade sein. Zum Beispiel sind 01101 und 11100011 Wörter von \(L_{\text{ung}}\), aber 0101 und 1000001 nicht.

Entwerfen Sie den Zustandsgraphen eines DEA, der die Sprache \(L_{\text{ung}}\) erkennt. Überprüfen Sie Ihren DEA mit einigen Eingaben.

Hilfe 1 (Was muss sich der DEA merken?):
Nicht die genaue Anzahl der Einsen, sondern nur, ob sie bisher gerade oder ungerade ist.
Hilfe 2 (Wirkung der Zeichen):
Was ändert eine 1 an dieser Information, was ändert eine 0?
Aufgabe 8: Zustandsgraphen für formale Sprachen (Einzelarbeit)

Erstellen Sie für die folgenden Sprachen je einen Zustandsgraphen eines deterministischen endlichen Automaten, welcher die jeweilige Sprache erkennt:

\(L = \{w \mid w \text{ beinhaltet das Teilwort } 010\}\)

Hilfe 1 (Fortschritt merken):
Die Zustände merken sich, wie viel von 010 schon gelesen wurde: nichts, „0“, „01“, „010“.
Hilfe 2 (Rückschritte):
Wird die Folge unterbrochen, beginnt sie nicht immer ganz von vorn: Nach „01“ und einer weiteren 1 ist nichts von 010 begonnen, nach „0“ und einer weiteren 0 aber schon wieder „0“.
Hilfe 3 (Nach dem Fund):
Ist 010 einmal gelesen, wird das Wort auf jeden Fall akzeptiert. Der Endzustand bekommt also eine Schleife für 0 und 1.

\(L = \{w \mid w \text{ beinhaltet höchstens dreimal } 1\}\)

Hilfe 1 (Zählen):
Die Zustände zählen die Einsen: 0, 1, 2, 3 und „mehr als 3“. Welche davon sind Endzustände?
Hilfe 2 (Nullen):
Eine 0 ändert die Anzahl der Einsen nicht.

\(L = \{w \mid w \text{ beinhaltet eine gerade Anzahl von } 1\}\)

Hilfe 1 (Vergleich):
Vergleichen Sie mit Aufgabe 7. Was ändert sich, wenn die Anzahl gerade statt ungerade sein soll?
Aufgabe 9: Formale Analyse zweier DEA (Partnerarbeit)

Gegeben sind die Zustandsgraphen von zwei DEA:

Zwei Zustandsgraphen zu Aufgabe 9 Zwei Zustandsgraphen zu Aufgabe 9
Abb.: Gegenüberstellung zweier Zustandsgraphen

Erstellen Sie die formalen Definitionen der DEA als 5-Tupel \((Q, \Sigma, \delta, s, F)\).

Hilfe 1 (Schema):
Gehen Sie für jeden DEA das 5-Tupel der Reihe nach durch: Q, Σ, δ (als Tabelle), s, F.
Hilfe 2 (Fehlende Übergänge):
Fehlt im Graphen ein Übergang, tragen Sie „–“ für den Fehlerzustand ein und vermerken das unter der Tabelle.

Geben Sie zu beiden DEA jeweils zwei Wörter an, die akzeptiert und zwei, die nicht akzeptiert werden.

Hilfe 1 (Akzeptierte Wörter):
Suchen Sie einen Weg vom Start- zu einem Endzustand und lesen Sie die Kantenbeschriftungen ab.
Hilfe 2 (Nicht akzeptierte Wörter):
Ändern Sie ein akzeptiertes Wort an einer Stelle und prüfen Sie, wo der DEA dann endet.

Geben Sie die jeweils akzeptierte Sprache entweder beschreibend oder in einer geschlossenen Form mit \(L = \{\dots\}\) an.

Hilfe 1 (Struktur):
Untersuchen Sie, welche Zeichenfolgen zum Endzustand führen und welche Schleifen es unterwegs gibt.
Hilfe 2 (Sackgassen):
Gibt es einen Zustand, von dem aus kein Endzustand mehr erreichbar ist? Er wirkt wie ein Fehlerzustand.
Hilfe 3 (Schreibweise):
Eine Beschreibung in Worten ist erlaubt. Für die Mengenschreibweise helfen Potenzen wie \(b^n\) für „n-mal b“.
🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Sie haben alle Aufgaben bearbeitet und abgehakt. Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.

Implementierung eines DEA in Java

gAeA Aufgabe 5 nur eA

Nun konstruieren wir eine algorithmische Umsetzung eines DEA in Java. Konkret betrachten wir den folgenden DEA, der Wörter über dem Eingabealphabet \(\Sigma = \{m, n\}\) verarbeitet:

Einstieg: Ein DEA als Datenstruktur

Aufgabe (Austausch mit benachbarten Personen): Wir wollen einen DEA algorithmisch modellieren. Vergleichen Sie die Struktur des Zustandsgraphen mit bekannten Datenstrukturen hinsichtlich Gemeinsamkeiten und Unterschieden.

gA Vergleich mit den linearen ADT (Stack, Queue, DynArray): Unter den bisher betrachteten ADT gibt es keinen direkten Vergleich. Es gibt aber einige Gemeinsamkeiten mit den linearen ADT:

Verkettete lineare Datenstruktur mit den Zeigern anf und pos
  • Gemeinsamkeiten: Zustände beim DEA entsprechen den Elementen der linearen ADT. Zustandsübergänge zu weiteren Zuständen entsprechen den Verweisen auf Nachfolgeelemente.
  • Unterschiede: Es gibt mehr als einen Nachfolger → die neue Datenstruktur ist nicht-linear. Die Verweise beim Zustandsgraphen haben eine zusätzliche Information, das Eingabezeichen für den Zustandsübergang.

eA Vergleich mit dem Binärbaum: Als Vergleich kommt nur ein Baum in Frage, hier ein Binärbaum, bei dem die Richtungen der Verweise eingezeichnet sind.

Binärbaum mit gerichteten Verweisen
  • Gemeinsamkeiten: Zustände beim DEA entsprechen den Knoten beim BinTree, Zustandsübergänge den Verweisen auf Nachfolgeknoten. Es kann mehr als einen Nachfolger geben → die Datenstruktur ist auch nicht-linear.
  • Unterschied: Die Verweise beim Zustandsgraphen haben eine zusätzliche Information, das Eingabezeichen für den Zustandsübergang.

Modellierung mit den Klassen State und Transition

Die Zustände (Knoten) bilden eine eigene Klasse State. Die Übergänge werden in einer eigenen Klasse Transition modelliert. Der DEA als solcher wird in einem Programm DEATest zusammengefügt. Das Klassendiagramm ist unten abgebildet.

State– t1 : Transition– t2 : Transition– end : booleanc State()+ changeEnd()+ setTransition(String s, Transition t)+ nextState(char c) : State+ getEnd() : booleanTransition– folge : State– eingabe : charc Transition(State s, char c)
Abb.: Klassendiagramm der Klassen State und Transition

Ein Objekt der Klasse State soll zunächst die folgenden Operationen ausführen können:

  1. Ändern können, ob es ein Endzustand ist.
  2. Ein Objekt der Klasse Transition an sich anfügen können, wobei die Transition und der Name der anzufügenden Transition als String übergeben werden.
  3. Mit einem übergebenen Zeichen einen Folgezustand ermitteln und diesen zurückgeben können.
  4. Antworten können, ob es ein Endzustand ist.

Aufgaben zur Implementierung eines DEA

Ihr Bearbeitungsfortschritt:0%

Aufgaben mit dem Zusatz „optional“ zählen nicht für die Fortschrittsanzeige. Bei Aufgabe 5 genügt eine der beiden Varianten.

Aufgabe 1: Klassen State und Transition (Partnerarbeit) gAeA

Die Klasse State wird die Klasse Transition beinhalten. Kopieren Sie die unvollständige Implementierung der Klasse State_unfertig und sichten Sie diese. Vervollständigen Sie die Operationen im Quellcode und benennen Sie die Klasse anschließend in State um.

public class State_unfertig {
  Transition t1;
  Transition t2;
  boolean end = false;

  public void changeEnd() {
    // changeEnd soll den aktuellen Wert von end umschalten.
  }

  public void setTransition(String s, Transition t) {
    // setTransition soll, wenn der übergebene Name t1 ist, die Transition t
    // t1 zuweisen, ansonsten t2.
    // Schwieriger: Beachten Sie, dass auch "falsche" Eingaben gemacht werden könnten.
  }

  public State nextState(char c) {
    // In Abhängigkeit des übergebenen Eingabezeichens soll der Folgezustand
    // zurückgegeben werden.
    // Schwieriger: Beachten Sie, dass auch "falsche" Eingaben gemacht werden könnten.
  }

  public boolean getEnd() {
    // Es soll zurückgegeben werden, ob der State ein Endzustand ist.
  }
}

class Transition {
  State folge;
  char eingabe;

  public Transition(State s, char c) {
    this.folge = s;
    this.eingabe = c;
  }
}
Hilfe 1 – Umschalten:
Ein boolescher Wert lässt sich mit einer Verzweigung (oder kürzer mit !) umschalten.
Hilfe 2 – Strings vergleichen:
Strings vergleicht man in Java mit s.equals("t1"), nicht mit ==.
Hilfe 3 – Folgezustand:
Vergleichen Sie das übergebene Zeichen mit t1.eingabe. Stimmt es überein, wird t1.folge zurückgegeben, sonst t2.folge.

Nun soll in einem weiteren Programm der m-n-DEA angelegt und getestet werden. Kopieren Sie die unvollständige Implementierung DEATest_unfertig und sichten Sie diese. Vervollständigen Sie den Quellcode entsprechend den Arbeitsschritten 1–8 im Programm und ändern Sie anschließend den Namen des Programms in DEATest.

// 1. Deklarieren und initialisieren Sie die notwendigen Zustände für den
//    m-n-DEA (Bsp.: State q0 = new State();).
// 2. Setzen Sie den Endzustand entsprechend.
// 3. Deklarieren und initialisieren Sie einen State aktuell und weisen Sie
//    diesem den Startzustand Ihres DEA zu.
// 4. Deklarieren und initialisieren Sie alle acht Transitionen (es würden auch
//    weniger reichen!) entsprechend dem m-n-DEA
//    (Bsp.: Transition u1 = new Transition(q1,'m');).
// 5. Weisen Sie nun den Zuständen die entsprechenden Transitionen zu.
// 6. Lesen Sie eine User-Eingabe für das Eingabewort ein und speichern Sie es ab.
// 7. Lesen Sie nacheinander die einzelnen Zeichen des Eingabewortes aus und
//    bilden Sie den jeweiligen Folgezustand.
// 8. Überprüfen Sie, ob nach Abarbeiten des Eingabewortes der letzte Zustand
//    ein Endzustand ist. Geben Sie aus, ob die Eingabe akzeptiert wurde.
Hilfe 1 – Fehlerzustand:
Der Zustand q3 ist ein Fehlerzustand (trap). Auch er benötigt zwei Transitionen, die wieder auf ihn selbst zeigen.
Hilfe 2 – Eingabewort abarbeiten:
for (int i = 0; i < s.length(); i++) { aktuell = aktuell.nextState(s.charAt(i)); }
Aufgabe 2: Jedes Zeichen mindestens zweimal (Einzelarbeit) gAeA

Ein Automat akzeptiert genau diejenigen Wörter, die aus den Zeichen a und b bestehen, in denen jedes Zeichen mindestens zweimal hintereinander steht. Die Sprache dieses Automaten wird mit \(L_1\) bezeichnet.

Entscheiden Sie, ob die Wörter aabb, aabbaaabb, abbb, a, bbbaaabb, bbabbb und bbbaab zu \(L_1\) gehören.

Hilfe 1 (Blöcke bilden):
Zerlegen Sie jedes Wort in Blöcke gleicher Zeichen, z. B. aabbaaabb = aa | bb | aaa | bb. Jeder Block muss mindestens zwei Zeichen lang sein.

Entwickeln Sie den Zustandsgraphen des Automaten und geben Sie seine formale Definition an.

Hilfe 1 (Was muss sich der DEA merken?):
Welches Zeichen gerade gelesen wird und ob es schon mindestens zweimal hintereinander kam.
Hilfe 2 (Wechsel):
Ein Wechsel von a nach b ist nur erlaubt, wenn der a-Block schon lang genug ist. Sonst führt der Übergang in den Fehlerzustand.

Erstellen Sie im Programm DEATest die benötigten Zustände und Übergänge.

Hilfe 1 (Vorlage):
Gehen Sie wie in Aufgabe 1 b) vor: Für jeden Zustand ein State-Objekt, für jeden Übergang ein Transition-Objekt.
Hilfe 2 (Fehlerzustand):
Auch der Fehlerzustand braucht ein State-Objekt mit zwei Transitionen, die auf ihn selbst zeigen.

Das Eingabealphabet des Automaten wird um das Zeichen c erweitert. Weiterhin werden nur Wörter akzeptiert, in denen jedes Zeichen mindestens zweimal aufeinanderfolgt. Entwickeln Sie einen entsprechenden Zustandsgraphen.

Hilfe 1 (Erweitern):
Für c kommen dieselben zwei Zustände hinzu wie für a und b. Von jedem „mindestens zweimal“-Zustand führt eine Kante mit c zum neuen „einmal c“-Zustand.

Implementieren Sie den Automaten aus d) mit Hilfe der Klasse State und dem Programm DEATest. Erstellen Sie hierfür eine dritte Transition in der Klasse State und passen Sie deren Operationen entsprechend an.

Hilfe 1 (Klasse State):
Ergänzen Sie ein Attribut t3 und erweitern Sie setTransition und nextState um eine weitere Verzweigung.
Aufgabe 3: DEA mit Switch-Case (Partnerarbeit) gAeA

Eine einfachere Variante, einen DEA algorithmisch umzusetzen, ist die Mehrfachverzweigung Switch-Case, die bereits bei den Aufgaben zum ADT Stack genutzt wurde.

Implementieren Sie den Automaten aus Aufgabe 2 b) (Alphabet {a, b}) mit Hilfe von Switch-Case. Wer 2 d) bearbeitet hat, setzt stattdessen den erweiterten Automaten über {a, b, c} um. Wenn Sie Hilfe benötigen, können Sie sich am freigegebenen Programm DEAsc orientieren und sich zusätzlich im Internet über Switch-Case informieren.

Hilfe 1 – Zustand als Zahl:
Speichern Sie den aktuellen Zustand in einer Variablen int zustand = 0;. Für jedes gelesene Zeichen wird mit switch(zustand) der Folgezustand bestimmt.
Hilfe 2 – Aufbau:
if (s.charAt(i) == 'a') { switch (zustand) { case 0: zustand = 1; break; case 1: zustand = 2; break; … } } – vergessen Sie das break; nicht.

Vergleichen Sie die beiden bisherigen Implementierungen eines DEA hinsichtlich ihrer Vor- und Nachteile.

Hilfe 1 (Gesichtspunkte):
Vergleichen Sie z. B. Umfang des Codes, Übersichtlichkeit, Aufwand bei einem zusätzlichen Zeichen und Nähe zum objektorientierten Modell.
Aufgabe 4 (optional): Das Zahlenschloss (Partnerarbeit) gAeA

Der DEA des Schlosssystems am Rüsselsspringergehege (Aufgabe 1 a) zu DEA, PINs 1059, 3064 und 0159) soll implementiert werden.

Verändern Sie die fertige Klasse State entsprechend.

Hilfe 1 (Anzahl der Transitionen):
Wie viele Eingabezeichen hat das Zahlenschloss? So viele Transitionen braucht jeder Zustand.

Legen Sie im Programm DEATest die benötigten Zustände und Übergänge an und verknüpfen Sie diese miteinander. Passen Sie die Ausgabe nach der Überprüfung sinnvoll an den Sachkontext an.

Hilfe 1 (Vorlage):
Nutzen Sie Ihren Zustandsgraphen aus Aufgabe 1 a) zu DEA. Alle falschen Ziffern führen in den Fehlerzustand.
Aufgabe 5: Ein DEA als Klasse mit dynamischen Reihungen (Partnerarbeit) eA

Die beiden bisherigen Varianten unterscheiden sich vor allem in ihrer Komplexität. Die Variante mit Switch-Case ist deutlich einfacher umzusetzen, die Klassen der ersten Variante passen dagegen eher zum objektorientierten Programmierparadigma – wirken aber recht unhandlich.

Bei beiden Varianten ist nachteilig, dass die Größe des Eingabealphabets und die Menge der Zustände nicht dynamisch erweiterbar sind. Ändert sich die Anzahl der Eingabezeichen, müsste man immer wieder den Java-Code verändern. Außerdem ist der DEA selbst nicht als Klasse modelliert. Dies ändert sich, wenn man mit dynamischen Reihungen (DynArray) arbeitet: Sie machen es möglich, mit beliebigen (aber endlich großen) Alphabeten und damit auch Zustandsübergängen zu arbeiten.

DEADyn– states : dynamische Reihung– alphabet : dynamische Reihung– akt : Ganzzahl– spos : Ganzzahlc DEADyn(n : Ganzzahl, s : Zeichenkette,t : statische Reihung vom Inhaltstyp Ganzzahl)+ setTransition(a : Ganzzahl, c : Zeichen, b : Ganzzahl)+ transition(c : Zeichen)+ getAktuell() : State+ simulate(word : Zeichenkette) : WahrheitswertState– folge : DynArray– eingabe : DynArray– end : booleanc State()+ setEnd()+ getEnd() : boolean+ getFolge(char c) : State
Abb.: Klassendiagramm der Klassen DEADyn und State

Wählen Sie eine der beiden Varianten aus. Wenn Sie eine Variante als erledigt abhaken, gilt Aufgabe 5 als erledigt.

a) Kopieren Sie die freigegebenen Klassen DEADyn, State und das Programm DEADynTest.

b) Führen Sie das Programm DEADynTest mit einigen Eingabewörtern aus.

c) Beschreiben Sie, was die Operation getFolge der Klasse State sowie der Konstruktor und die Operationen setTransition, transition und simulate der Klasse DEADyn bei ihrem Aufruf ausführen.

d) Implementieren Sie den DEA aus Aufgabe 2 d) und den DEA des Schlosssystems (Aufgabe 1 a) zu DEA) mit der neuen Variante.

a) Die Klasse State hat die Attribute folge (Menge der Folgezustände) und eingabe (zugehörige Eingabezeichen) sowie das Attribut end, das angibt, ob es sich um einen Endzustand handelt. Außer dem Standardkonstruktor gibt es keinen weiteren, da die Transitionen in der Klasse DEADyn gesetzt werden. Kopieren Sie die Klasse State_unfertig, vervollständigen Sie sie und benennen Sie sie in State um.

b) Die Attribute states und alphabet speichern die Zustände des DEA und die Eingabezeichen. Der aktuelle Zustand wird unter akt gespeichert, spos ist eine Hilfsvariable zum Durchlaufen der dynamischen Reihungen. Beim Aufruf des Konstruktors werden zunächst n Zustände initialisiert und an states angehängt. Anschließend werden die Zeichen des Eingabealphabets aus dem String s an alphabet angehängt. Das int-Array t enthält die Endzustände, z. B. {1, 5, 13}. Kopieren Sie die Klasse DEADyn_unfertig.

c) Implementieren Sie die Attribute und den Konstruktor der Klasse DEADyn_unfertig und benennen Sie die Klasse in DEADyn um.

d) Die Operation setTransition(a, c, b) soll beim Zustand am Index a von states als Folgezustand b bei der Eingabe c speichern. Die Operation getAktuell soll den Zustand zurückgeben, in dem sich der DEA gerade befindet. Implementieren Sie beide Operationen.

e) Die Operation transition(char z) soll den Automaten in den Folgezustand versetzen, den er bei Eingabe von z einnehmen muss. Implementieren Sie diese Operation.

f) Die Operation simulate(String word) soll das Eingabewort überprüfen und true zurückgeben, wenn es akzeptiert wird, ansonsten false. Implementieren Sie diese Operation.

g) Implementieren Sie den DEA aus Aufgabe 2 d) und den DEA des Schlosssystems mit der neuen Variante.

🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Sie haben alle Aufgaben bearbeitet und abgehakt. Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.

Mealy-Automaten

Die Zoodirektorin des Osnabrücker Zoos hat die Idee, einen Futterautomaten für die Rüsselsspringer anzuschaffen. Mit diesem können Besuchende des Zoos kleine Snacks für die Tiere kaufen. Der Automat hat einen Münzschlitz, in den nur 10 oder 20 Cent Münzen eingeworfen werden können.

Rüsselsspringer beim Fressen von Himbeeren
Bild von einer KI erstellt

Über eine Reset-Taste kann der Kaufvorgang abgebrochen werden und der Automat gibt das eingezahlte Geld wieder zurück. Als Snacks stehen Blaubeeren (10 Cent) und Himbeeren (20 Cent) zur Verfügung, welche man über eine entsprechende Taste auswählen kann. Mehr als insgesamt 20 Cent kann man nicht einwerfen. Zu viel gezahltes Geld wird direkt wieder ausgegeben.

Aufgabe (Austauschphase → Lerngruppe)

Die grundlegende Funktionsweise des Futterautomaten ist im unten abgebildeten Zustandsgraphen dargestellt. Ein \(\epsilon\) als Ausgabe bedeutet, dass nichts ausgegeben wird. Der Zustand kann sich dabei trotzdem ändern.

Zustandsgraph des Futterautomaten

Sicherung: Bearbeiten Sie zuerst die Aufgabenteile a) und b). Danach finden Sie hier die Beschreibung des neuen Automatentyps, seine formale Definition und den korrigierten Automaten als Tabelle.

Aufgaben zu Mealy-Automaten

Arbeiten Sie die folgenden Aufgabenstellungen zu Mealy-Automaten durch. Nutzen Sie bei Bedarf die integrierten Hilfestellungen.

Ihr Bearbeitungsfortschritt: 0%
Aufgabe 1: Erweiterung des Futterautomaten (Einzel- oder Partnerarbeit)

Da der Futterautomat für die Rüsselsspringer bei den Gästen des Zoos sehr gut angekommen ist, soll er erweitert werden. Nun kann man 10, 20 und 50 Cent einwerfen. Die Futteroptionen sind nun um Melonenstücke (M) für 50 Cent erweitert worden. Nach wie vor wird zu viel eingeworfenes Geld automatisch zurückgegeben und der Automat akzeptiert maximal 50 Cent Guthaben. Die Returntaste gibt es ebenfalls wieder.

Rüsselsspringer im Zoo mit Melone
Bild von einer KI erzeugt

Entwerfen Sie einen Mealy-Automaten in Form eines Zustandsgraphen, der die neuen Anforderungen umsetzt.

Tipp (Zustände):
Legen Sie für jedes mögliche Guthaben einen Zustand an: \(q_0\) (0 Cent), \(q_1\) (10 Cent), \(q_2\) (20 Cent), \(q_3\) (30 Cent), \(q_4\) (40 Cent), \(q_5\) (50 Cent).
Tipp (Ausgaben bei Überzahlung):
Wenn in Zustand \(q_4\) (40 Cent) noch 20 Cent eingeworfen werden, wechselt der Automat in \(q_5\) und gibt sofort 10 Cent Wechselgeld zurück (Beschriftung der Kante: 20 / 10).

Geben Sie die formale Definition Ihres Mealy-Automaten als 6-Tupel \((Q, \Sigma, \Omega, \delta, \lambda, s)\) an.

Hilfe 1 (Schema):
Gehen Sie das 6-Tupel der Reihe nach durch: Q, Σ, Ω, δ, λ, s. δ und λ lassen sich gemeinsam in einer Tabelle mit Einträgen „Folgezustand, Ausgabe“ angeben.
Hilfe 2 (Ausgabealphabet):
Ω enthält alle Ausgaben, die vorkommen. „Keine Ausgabe“ wird als ε notiert, gehört aber nicht zu Ω.
Aufgabe 2: Fehlerhafter Ticketautomat (Einzel- oder Partnerarbeit)

Der Ticketautomat im Osnabrücker Zoo verursacht regelmäßig Beschwerden von Kundinnen und Kunden. Irgendwie scheint seine Funktionalität nicht in Ordnung zu sein. Der Mealy-Automat, der die Ticketvergabe steuert, ist unten abgebildet:

Mealy-Automat zur Ticketvergabe
Abb.: Mealy-Automat zur Ticketvergabe im Zoo

Analysieren und erläutern Sie die Funktionsweise dieses Mealy-Automaten. Decken Sie dabei logische Fehler oder unerwünschtes Verhalten im Ablauf auf.

Hilfe 1 (Zustände deuten):
Überlegen Sie für jeden Zustand, welches Guthaben er darstellt. Passen die Namen der Zustände dazu?
Hilfe 2 (Testen):
Spielen Sie einige Einwürfe durch, z. B. 2 €, 2 €, 2 €. Was kostet das Ticket dann, und gibt es Wechselgeld?
Hilfe 3 (Fehlende Funktionen):
Was passiert, wenn jemand den Kauf abbrechen möchte?

Erläutern Sie, weshalb ein Mealy-Automat generell keine Fehler- und Endzustände besitzt.

Hilfe 1 (Aufgabe des Automaten):
Ein DEA entscheidet, ob ein Wort akzeptiert wird. Was ist dagegen die Aufgabe eines Mealy-Automaten?

Entwickeln Sie Vorschläge zur Verbesserung und verändern Sie den Zustandsgraphen entsprechend. Integrieren Sie auch die Möglichkeit, mit einem 5 €-Schein zu zahlen.

Hilfe 1 (Vorgehen):
Legen Sie zuerst fest, was das Ticket kostet und welche Eingaben es gibt (Münzen, Schein, Rückgabe). Dann erhält jeder Zustand für jede Eingabe eine Kante.
Hilfe 2 (Ausgaben):
Eine Ausgabe wie „Ticket, 1 €“ darf ein einziges Ausgabezeichen sein.
Aufgabe 3: Analyse eines formal definierten Mealy-Automaten (Einzelarbeit)

Gegeben ist ein Mealy-Automat mit \(Q=\{q_0, q_1, q_2\}\), \(\Sigma=\{0,1\}\), \(\Omega=\{0,1\}\) und Startzustand \(s=q_0\). Die Zustandsübergangs- (\(\delta\)) und Ausgabefunktionen (\(\lambda\)) sind in den folgenden Tabellen dargestellt:

\(\delta\)01
\(q_0\)\(q_0\)\(q_1\)
\(q_1\)\(q_2\)\(q_1\)
\(q_2\)\(q_2\)\(q_0\)
\(\lambda\)01
\(q_0\)01
\(q_1\)10
\(q_2\)01

Zeichnen Sie den zugehörigen Zustandsgraphen auf ein Blatt Papier oder in Ihr Digitalheft.

Hilfe 1 (Vorgehen):
Zeichnen Sie die drei Zustände. Lesen Sie dann in den Tabellen Zeile für Zeile ab: Aus δ den Folgezustand, aus λ die Ausgabe. Jede Kante wird „Eingabe / Ausgabe“ beschriftet.

Überprüfen Sie, welche Ausgaben durch die folgenden Eingabefolgen nacheinander erzeugt werden:

  1. 11111
  2. 01011
  3. 1010
Hilfe 1 (Tabelle führen):
Notieren Sie für jedes Zeichen: aktueller Zustand, Eingabe, Ausgabe, Folgezustand. Beginnen Sie jede Folge in \(q_0\).
Aufgabe 4: Modellierung eines Blumenautomaten (Einzel- oder Partnerarbeit)

Ein neuer Blumenautomat bietet zwei Sorten Blumen \(B_1\) und \(B_2\) an. Beide Sträuße kosten jeweils 3 €. Eine Kundin bzw. ein Kunde kann nur 1 € oder 2 € Münzen einwerfen. Der Automat besitzt zwei Tasten \(T_1\) und \(T_2\) für die beiden Straußvarianten sowie eine Taste \(R\) für die Rückgabe des eingeworfenen Geldes. Zu viel eingeworfenes Geld (man kann maximal 3 Euro Guthaben haben) wird sofort wieder zurückgegeben.

Blumenautomat im Bahnhof
Abb.: Automatisierter Blumenverkauf

Entwickeln Sie den Zustandsgraphen eines Mealy-Automaten, der die gesamte Logik des Blumenautomaten korrekt umsetzt.

Hilfe 1 (Zustände):
Die Zustände stehen für das Guthaben: 0 €, 1 €, 2 €, 3 €.
Hilfe 2 (Tasten):
Was passiert, wenn eine Taste gedrückt wird, obwohl das Guthaben nicht reicht? Und was gibt R in jedem Zustand aus?
Hilfe 3 (Zu viel Geld):
Bei 2 € Guthaben und einer 2-€-Münze werden 3 € erreicht. Der überzählige Euro wird sofort ausgegeben.

Geben Sie die formale Definition des Mealy-Automaten an.

Hilfe 1 (Schema):
Gehen Sie das 6-Tupel durch: Q, Σ, Ω, δ, λ, s. Eine gemeinsame Tabelle für δ und λ ist am übersichtlichsten.
Aufgabe 5: Simulation eines Kaffeeautomaten (Einzel- oder Partnerarbeit)

Entwickeln Sie einen endlichen Automaten mit Ausgabe zur Simulation des dargestellten Kaffeeautomaten. Der Automat akzeptiert nur 0,50 €- und 1,00 €-Münzen. Ein kleiner Kaffee kostet 1 € und ein großer Kaffee 2 €. Man kann nicht mehr als 2 € Guthaben besitzen.

Kaffeeautomat im Café
Abb.: Moderner Kaffeeautomat mit Displaysteuerung

Wählen Sie eine der beiden Varianten zur Bearbeitung aus:

StandardvarianteSchwierige Variante
Es gibt keine Geldrückgabe. Es gibt eine Geldrückgabe mit einer zusätzlichen Taste. Zu viel eingeworfenes Geld kommt automatisch wieder heraus.

Entwerfen Sie den Zustandsgraphen für die gewählte Variante.

Hilfe 1 (Zustände):
Die Zustände stehen für das Guthaben in 50-Cent-Schritten: 0 €, 0,50 €, 1 €, 1,50 €, 2 €.
Hilfe 2 (Eingaben):
Eingaben sind die beiden Münzen und die Tasten für kleinen und großen Kaffee (in der schwierigen Variante auch die Rückgabetaste). Jeder Zustand braucht für jede Eingabe eine Kante.
Aufgabe 6: Hintergrund und Signalton in einer App (Einzel- oder Partnerarbeit)

In einer Smartphone-App kann man einen Hintergrund (A oder B) und einen Signalton (1 oder 2) auswählen und anschließend herunterladen. Interpretieren Sie die Funktionsweise des Auswahlbildschirms als Mealy-Automat, wobei die Eingabe durch Antippen der Schaltflächen HA, HB (Hintergrund A/B), T1, T2 (Ton 1/2) und OK zu verstehen ist. Die Schaltflächen können mehrfach angetippt werden. Durch Antippen ändert sich die aktuelle Auswahl. Wird keine Schaltfläche angetippt, ist die Situation wie in der Abbildung. Durch Antippen von „OK“ startet der Download des ausgewählten Hintergrunds und Signaltons.

Downloads
Hintergrund
HA ✓HB
Signalton
T1 ✓T2
OK
Abb.: Auswahlbildschirm der App in der Grundeinstellung (Hintergrund A, Ton 1)

Entwerfen Sie einen Mealy-Automaten, der die Funktionsweise dieser Menüauswahl und den anschließenden Download-Start korrekt umsetzt.

Hilfe 1 (Zustände):
Ein Zustand ist eine Kombination aus gewähltem Hintergrund und gewähltem Ton. Wie viele Kombinationen gibt es?
Hilfe 2 (Kanten):
Antippen von HA, HB, T1 oder T2 ändert höchstens die Auswahl und gibt nichts aus (ε). Nur OK erzeugt eine Ausgabe.
Aufgabe 7: Baumstamm-Längentest am Förderband (Einzel- oder Partnerarbeit)
Längentest von Baumstämmen am Förderband
Abb.: Messanordnung mit den drei Lichtschranken A, B und C

Ein Förderband zum Längentest von Baumstämmen enthält die drei Lichtschranken A, B und C. Baumstämme haben die richtige Länge, wenn sie länger oder genau so lang wie die Messstrecke \(\overline{AB}\), aber kürzer als die Messstrecke \(\overline{AC}\) sind. Zwei aufeinander folgende Stämme werden so auf das Förderband gelegt, dass ihr Abstand größer als \(\overline{AC}\) ist. Bei Einschalten des Bandes sei kein Stamm auf dem Förderband. Kein Stamm ist kürzer als \(\overline{BC}\). Die Lichtschranken liefern die Signale 0 und 1. Das Tripel 011 bedeutet, dass ein Stamm den Messpunkt A vollständig durchfahren hat, sich aber noch im Bereich der Messpunkte B und C befindet. Diese Tripel werden in regelmäßiger Folge an einen Automaten weitergeleitet.

Skizze der Lichtschranken A, B, C am Förderband

Interpretieren Sie folgende Tripelfolgen bezüglich der Stammlängen, in denen nur die Übergänge, jedoch nicht sich wiederholende Tripel aufgeführt sind:

i) \(000 \rightarrow 100 \rightarrow 110 \rightarrow 111 \rightarrow 011 \rightarrow 001 \rightarrow 000\)

ii) \(000 \rightarrow 100 \rightarrow 010 \rightarrow 011 \rightarrow 001 \rightarrow 000\)

Hilfe 1 (Tripel lesen):
Jedes Tripel gibt an, welche Lichtschranken gerade unterbrochen sind (A, B, C; 1 = unterbrochen).
Hilfe 2 (Länge ablesen):
Bedeckt der Stamm irgendwann A und C gleichzeitig, ist er mindestens so lang wie \(\overline{AC}\). Verlässt er A, bevor er B erreicht, ist er kürzer als \(\overline{AB}\).

Geben Sie begründet eine Tripelfolge an, die in der Realität aufgrund der physikalischen Anordnung nicht auftreten kann.

Hilfe 1 (Anordnung):
B liegt zwischen A und C. Welche Kombination kann ein einzelner Stamm deshalb nie erzeugen?

In Abhängigkeit von der eingegangenen Tripelfolge gibt der Automat folgende Ausgaben:

  • + Stamm ist zu lang
  • - Stamm ist zu kurz
  • 0 Stamm hat die richtige Länge
  • n Stamm nicht im Bereich der Lichtschranken oder Länge noch nicht feststellbar
Abb.: Mealy-Automat zur Längenprüfung am Förderband

1. Begründen Sie, warum das Tripel 101 nicht im Eingabealphabet enthalten ist.

2. Interpretieren Sie die Zustände \(q_1\) bis \(q_4\) und \(q_6\) des Automaten.

Tipp zu 1 (Ausschließen von 101):
Überlegen Sie, was das Signal 101 bedeuten würde: Lichtschranke A ist unterbrochen, Lichtschranke B frei, Lichtschranke C unterbrochen. Warum ist das bei einem einzelnen zusammenhängenden Baumstamm unmöglich?
Tipp zu 2 (Bedeutung der Zustände):
Betrachten Sie, welche Lichtschranke ein Stamm bereits erreicht hat, während er sich durch die Messstrecke bewegt (z. B. \(q_1\): Stamm hat A unterbrochen; \(q_2\): Stamm unterbricht A und B gleichzeitig; etc.).
🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Sie haben alle Aufgaben bearbeitet und abgehakt. Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.

Grenzen endlicher Automaten

Einstiegsaufgabe: Grenzen der Automaten untersuchen (Arbeitsteilige Partner- oder Gruppenarbeit)

Wählen Sie eine der beiden Varianten über die Reiter aus und bearbeiten Sie die dazugehörigen Teilaufgaben:

Standardvariante
Fortschritt Standardvariante: 0%

Aufgrund des hohen Futterbedarfs der sehr vielen neu geborenen Rüsselsspringerbabies soll der Futterautomat so geändert werden, dass die Menge des eingeworfenen Geldes nicht begrenzt ist. Dazu reduziert man die möglichen Münzen auf 10 Cent. Zu kaufen gibt es nur noch preisreduzierte Himbeeren für 10 Cent. Eine Resettaste gibt es nicht mehr.

Rüsselsspringer im Zoo

Zusammenfassung für beide Varianten

Am Beispiel des Futterautomaten erkennt man, dass manche Situationen nicht mit endlichen Automaten zu realisieren sind.

Für jede Erhöhung des maximalen Guthabens um 10 Cent wäre ein weiterer Zustand notwendig:

Zustandsgraph mit unendlich vielen Zuständen
Abb.: Notwendigkeit unendlich vieler Zustände bei unbegrenzter Eingabe

Somit bräuchte der Automat unendlich viele Zustände, um jedes mögliche Guthaben korrekt verarbeiten zu können. Sowohl ein DEA als auch ein Mealy-Automat können dies nicht leisten, da sie in ihrer Funktionsweise und durch die nur endlich mögliche Zustandsmenge hierfür nicht hinreichend funktional sind.

Aufgabe: Vom DEA zum Kellerautomaten

eA

Kellerautomaten gehören zum erhöhten Anforderungsniveau. Im grundlegenden Anforderungsniveau endet der Abschnitt mit der Zusammenfassung oben: Endliche Automaten können sich nur endlich viel merken.

Fortschritt Kellerautomat: 0%

Die Situation entspricht der Standardvariante der Einstiegsaufgabe: Wir benötigen einen Automaten, der ein beliebiges, aber endliches Guthaben korrekt verarbeiten kann.

🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Sie haben alle Aufgaben bearbeitet und abgehakt. Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.

Nichtdeterministische Kellerautomaten (NKA)

eA

Wir erweitern nun unsere bekannten Automaten um eine neue Klasse. Der zuletzt betrachtete Automat aus der Aufgabe „Vom DEA zum Kellerautomaten“ kann auch als Zustandsgraph dargestellt werden:

Aktuelles Eingabezeichen(10,H):ε(10,10):1010Oberstes StapelzeichenStapeloperation(das gelesene und das entfernteZeichen kommen wieder auf den Keller)q0q1q2Start(#,10):10#(#,ε):#(#,10):10#
Abb.: Der Himbeerautomat als Kellerautomat

Generell gilt:

  • Jede Kante ist so beschriftet: (oberstes Kellerzeichen, Eingabezeichen) : abzulegende Zeichen.
  • Das gelesene oberste Kellerzeichen wird immer mit pop() entfernt.
  • Mit push() können auch mehrere Zeichen auf den Keller gelegt werden. Das am weitesten rechts notierte Zeichen kommt zuerst auf den Keller: Bei 10# wird zuerst # und anschließend 10 abgelegt.
  • Ein \(\varepsilon\) als Eingabezeichen bedeutet, dass der Automat kein Zeichen liest und nur in Abhängigkeit vom obersten Kellerzeichen entscheidet, ob er den Übergang wählt (\(\varepsilon\)-Übergang). Im Beispiel geht es von \(q_1\) nach \(q_2\), wenn im Keller nur noch das Vorbelegungszeichen # liegt, das Guthaben also aufgebraucht ist.
  • Ein \(\varepsilon\) als abzulegende Zeichen bedeutet, dass nichts abgelegt wird. Das gelesene, also mit pop() entfernte Zeichen ist dann vom Keller verschwunden.
  • Gibt es für die aktuelle Situation keinen passenden Übergang, bricht der Automat ab. Das Wort wird auf diesem Weg nicht akzeptiert.
  • Ein Wort wird akzeptiert, wenn der Automat das ganze Wort lesen kann und sich danach in einem Endzustand befindet.
Man beachte, dass die Höhe des zur Verfügung stehenden Guthabens bei dieser Arbeitsweise beliebig groß sein kann. Der ADT Stapel passt sich dynamisch jeder Größe an!

Die Regel (#,10):10# im Zustand \(q_0\) interpretiert man wie folgt: Aktueller Zustand \(q_0\), gelesenes Stapelzeichen #, aktuelles Eingabezeichen 10 → Folgezustand \(q_1\), Stapeloperation push(#) und push(10). Befindet sich der Automat also im Zustand \(q_0\), liest das Eingabezeichen 10 und liegt im Keller nur das Vorbelegungszeichen #, wechselt er in den Zustand \(q_1\), legt # zurück und legt zusätzlich die 10 auf den Stapel.

Epsilon-Übergänge (\(\varepsilon\)-Übergänge) sind spezielle Übergänge, die ohne das Lesen eines Eingabesymbols erfolgen. Der Automat kann so seinen Zustand ändern und/oder den Keller manipulieren, ohne dass ein Zeichen aus der Eingabe gelesen wird. Das ist nützlich, um Zustandsänderungen zu ermöglichen, die nur von der aktuellen Kellerkonfiguration abhängen. Achtung: Existiert in einem deterministischen Kellerautomaten von einem Zustand ein \(\varepsilon\)-Übergang, darf es von diesem Zustand aus keinen weiteren Übergang mit dem gleichen Kellersymbol geben.
Nichtdeterminismus: Bei einem Kellerautomaten dürfen in einer Situation mehrere Übergänge passen, z. B. zwei Kanten mit (#,a) zu verschiedenen Folgezuständen oder eine Kante mit (#,a) neben einer \(\varepsilon\)-Kante mit (#,ε). Der Automat kann dann jeden dieser Übergänge wählen. Jede mögliche Folge von Übergängen heißt Rechenweg. Ein Wort wird akzeptiert, wenn es mindestens einen Rechenweg gibt, auf dem das Wort vollständig gelesen wird und der Automat danach in einem Endzustand ist. Rechenwege, die abbrechen oder nicht in einem Endzustand enden, spielen dann keine Rolle.
Der Himbeerautomat ist deterministisch: In jeder Situation passt höchstens ein Übergang. Es gibt aber Sprachen, die nur ein nichtdeterministischer Kellerautomat erkennen kann, weil er beim Lesen „raten“ muss, welcher Fall vorliegt (siehe Aufgabe 9 unten).
Aufgabe (Austauschphase → Lerngruppe): Vervollständigen Sie die Tabelle für die Zustandsübergangsfunktion des Himbeerautomaten. Die erste Regel lautet: Zustand \(q_0\), #, 10 → Zustand \(q_1\), push(#) und push(10). Stellen Sie die übrigen vier Regeln entsprechend auf.
RegelZustandStapel obenEingabeFolgezustandStapeloperation
1\(q_0\)#10\(q_1\)push(#), push(10)
2\(q_1\)1010\(q_1\)push(10), push(10)
3\(q_1\)10H\(q_1\)– (nur pop)
4\(q_1\)#\(\varepsilon\)\(q_2\)push(#)
5\(q_2\)#10\(q_1\)push(#), push(10)

Die folgende Abbildung zeigt Schritt für Schritt, wie der Himbeerautomat eine gültige und eine ungültige Eingabe verarbeitet: Welches Zeichen gelesen wird, welche Regel greift, in welchem Zustand sich der Automat befindet und was dabei auf dem Keller passiert.

Legende: nächstes Eingabezeichen · aktueller Zustand · oberstes Kellerzeichen · in diesem Schritt vom Keller entnommen · in diesem Schritt abgelegt
Regelnummern wie in der Tabelle oben. Schreibweise: (oberstes Kellerzeichen, Eingabezeichen) : abzulegende Zeichen. Das gelesene oberste Kellerzeichen wird dabei immer entfernt; von den abzulegenden Zeichen kommt das am weitesten rechts notierte zuerst auf den Keller.
Im Zustandsgraphen über jedem Lauf steht R1 bis R5 für Regel 1 bis 5. 1 zeigt, in welchem Schritt die Regel angewendet wird; grau gezeichnete Übergänge kommen in diesem Lauf nicht vor; rot gestrichelt ist ein Übergang, den es nicht gibt: Dort bricht der Automat ab.
Tipp: Fahren Sie mit der Maus über einen Regelpfeil oder tippen Sie ihn an: Der Schritt wird erklärt und der passende Übergang im Zustandsgraphen hervorgehoben.
Gültige Verarbeitung: 10 10 H H
Zweimal 10 Cent einwerfen, zweimal die Himbeertaste drücken.
Startq0q1q2R1 (#,10):10#1R2 (10,10):10102R3 (10,H):ε34R4 (#,ε):#5R5 (#,10):10#
Schritt 0 · StartEingabe1010HHZustandq0q1q2Keller#oben
Regel 1(#,10):10#liest 10nimmt # weg
legt 10# ab
Regel 1 in q0: Oben im Keller liegt #, gelesen wird 10. Das gelesene # wird aus dem Keller entfernt. Hinter dem Doppelpunkt steht 10#: Das am weitesten rechts notierte Zeichen kommt zuerst auf den Keller, also erst #, dann 10. Der Automat wechselt nach q1. Die 10 im Keller steht für 10 Cent Guthaben.
Schritt 1Eingabe1010HHZustandq0q1q2Keller#10entnommen#oben
Regel 2(10,10):1010liest 10nimmt 10 weg
legt 1010 ab
Regel 2 in q1: Oben liegt 10, gelesen wird wieder 10. Die gelesene 10 wird entfernt, abgelegt wird 1010, also zwei Zehner. Im Keller liegen jetzt zwei Münzen, also 20 Cent Guthaben. Der Zustand bleibt q1.
Schritt 2Eingabe1010HHZustandq0q1q2Keller#1010entnommen10oben
Regel 3(10,H):εliest Hnimmt 10 weg
legt nichts ab
Regel 3 in q1: Oben liegt 10, gelesen wird H. Die gelesene 10 wird entfernt, hinter dem Doppelpunkt steht ε: Es wird nichts abgelegt. Die Himbeere ist damit bezahlt, es bleiben 10 Cent Guthaben. Der Zustand bleibt q1.
Schritt 3Eingabe1010HHZustandq0q1q2Keller#10entnommen10oben
Regel 3(10,H):εliest Hnimmt 10 weg
legt nichts ab
Regel 3 in q1: Wieder liegt 10 oben und H wird gelesen. Die letzte 10 wird entfernt und nichts abgelegt, oben liegt nur noch #: Das Guthaben ist aufgebraucht. Die Eingabe ist jetzt vollständig gelesen.
Schritt 4Eingabe1010HHvollständig gelesenZustandq0q1q2Keller#entnommen10oben
Regel 4(#,ε):#liest nichts (ε)nimmt # weg
legt # ab
Regel 4 in q1: Oben liegt #. Das ist ein ε-Übergang: Es wird kein Eingabezeichen gelesen. Das gelesene # wird entfernt und wieder abgelegt, der Keller sieht also aus wie vorher. Der Automat wechselt nach q2 („Guthaben aufgebraucht“). Die Eingabe ist vollständig verarbeitet und q2 ist Endzustand: Das Wort wird akzeptiert.
Schritt 5 · EndeEingabe1010HHvollständig gelesenZustandq0q1q2Keller#entnommen#oben
Akzeptiert: Es gibt eine Möglichkeit, die Eingabe vollständig zu verarbeiten, sodass sich der Automat danach im Endzustand \(q_2\) befindet. Auf dem Keller liegt nur noch das Vorbelegungszeichen #, das Guthaben ist also genau verbraucht.
Ungültige Verarbeitung: 10 H H
Einmal 10 Cent einwerfen, aber zweimal die Himbeertaste drücken.
Start(#,H)✕Abbruch4q0q1q2R1 (#,10):10#1R2 (10,10):1010R3 (10,H):ε2R4 (#,ε):#3R5 (#,10):10#
Schritt 0 · StartEingabe10HHZustandq0q1q2Keller#oben
Regel 1(#,10):10#liest 10nimmt # weg
legt 10# ab
Regel 1 in q0: Oben im Keller liegt #, gelesen wird 10. Das gelesene # wird aus dem Keller entfernt. Hinter dem Doppelpunkt steht 10#: Das am weitesten rechts notierte Zeichen kommt zuerst auf den Keller, also erst #, dann 10. Der Automat wechselt nach q1. Die 10 im Keller steht für 10 Cent Guthaben.
Schritt 1Eingabe10HHZustandq0q1q2Keller#10entnommen#oben
Regel 3(10,H):εliest Hnimmt 10 weg
legt nichts ab
Regel 3 in q1: Oben liegt 10, gelesen wird H. Die gelesene 10 wird entfernt und nichts abgelegt, die erste Himbeere ist bezahlt. Oben liegt nur noch #: Es gibt kein Guthaben mehr, in der Eingabe wartet aber noch ein H.
Schritt 2Eingabe10HHZustandq0q1q2Keller#entnommen10oben
Regel 4(#,ε):#liest nichts (ε)nimmt # weg
legt # ab
Regel 4 in q1: Oben liegt #. Regel 4 ist ein ε-Übergang: Sie liest kein Eingabezeichen, sondern hängt nur vom Zustand q1 und dem # oben ab. Das H wird also nicht verarbeitet, es bleibt stehen und ist im nächsten Schritt dran. Das gelesene # wird entfernt und wieder abgelegt, der Automat wechselt nach q2.
Schritt 3Eingabe10HHZustandq0q1q2Keller#entnommen#oben
kein Übergang(#,H) in q2H nicht lesbar→ AbbruchKein passender Übergang: In q2 gibt es nur Regel 5 (#,10), hier darf also nur Geld eingeworfen werden. Für # oben und das Eingabezeichen H gibt es keinen Übergang. Der Automat bricht ab: Das zweite H kann nicht mehr gelesen werden, das Wort wird also nicht vollständig gelesen und nicht akzeptiert. Ohne Regel 4 wäre es genauso: Auch in q1 gibt es keinen Übergang für (#,H).
Schritt 4Eingabe10HHvollständig gelesenZustandq0q1q2✗ FehlerzustandKeller#oben
Nicht akzeptiert: Nach dem ersten H ist das Guthaben verbraucht, auf dem Keller liegt nur noch #. Über den ε-Übergang (Regel 4) wechselt der Automat nach \(q_2\), ohne dabei ein Zeichen zu lesen. Für (#,H) gibt es in \(q_2\) keinen Übergang, der Automat bricht ab, bevor das zweite H gelesen ist. Auch ohne Regel 4 gäbe es in \(q_1\) keinen Übergang für (#,H). Es gibt also keinen Rechenweg, der das ganze Wort liest und in einem Endzustand endet.
Abb.: Schrittweise Verarbeitung einer gültigen und einer ungültigen Eingabe durch den Himbeerautomaten

Formale Definition eines NKA

Ein solcher Automat heißt nichtdeterministischer Kellerautomat (NKA), englisch pushdown automaton. Seine formale Definition ist ein 7-Tupel \((Q, \Sigma, \Gamma, \delta, s, \#, F)\), wobei die einzelnen Komponenten wie folgt definiert sind:

DefinitionHimbeerautomat
\(Q\)\(Q\) ist eine nicht leere, endliche Menge von Zuständen, in denen sich der Kellerautomat befinden kann.\(Q = \{q_0, q_1, q_2\}\)
\(\Sigma\)\(\Sigma\) ist ein nicht leeres, endliches Eingabealphabet. Das leere Wort \(\varepsilon\) gehört nicht dazu.\(\Sigma = \{10, H\}\)
\(\Gamma\)\(\Gamma\) ist ein nicht leeres, endliches Kelleralphabet. Es enthält alle Zeichen, die im Keller liegen können.\(\Gamma = \{\#, 10\}\)
\(\delta\)\(\delta\) ist die Übergangsrelation. Sie ordnet jeder Kombination aus aktuellem Zustand, Eingabezeichen oder \(\varepsilon\) und oberstem Kellerzeichen eine (eventuell leere) Menge von Möglichkeiten zu. Jede Möglichkeit besteht aus einem Folgezustand und den abzulegenden Zeichen. Enthält eine Menge mehr als eine Möglichkeit, arbeitet der Automat nichtdeterministisch.siehe Tabelle der Aufgabe oben, z. B. \(\delta(q_0, 10, \#) = \{(q_1, 10\#)\}\)
\(s\)\(s \in Q\) ist der Startzustand, in dem sich der Kellerautomat zu Beginn befindet.\(s = q_0\)
\(\#\)\(\# \in \Gamma\) ist das Vorbelegungszeichen: Zu Beginn liegt nur \(\#\) im Keller.\(\#\)
\(F\)\(F \subseteq Q\) ist die Menge der akzeptierenden Zustände (Endzustände). Es darf auch mehrere Endzustände geben.\(F = \{q_2\}\)

Aufgaben zu Grenzen endlicher Automaten – NKA

eA

Ihr Bearbeitungsfortschritt:0%
Aufgabe 1: Einen NKA analysieren (Partnerarbeit)

In der Abbildung sehen Sie den Zustandsgraphen eines NKA. Ein leeres Wort wird auch akzeptiert.

Erstellen Sie die formale Notation des NKA in Form eines 7-Tupels.

Hilfe 1 (Schema):
Gehen Sie das 7-Tupel der Reihe nach durch: Q, Σ, Γ, δ, s, #, F. Γ enthält alle Zeichen, die im Keller liegen können.
Hilfe 2 (Regeln):
Legen Sie für δ eine Tabelle an: Zustand, oberstes Kellerzeichen, Eingabe, Folgezustand, abzulegende Zeichen. Jede Zeile einer Kantenbeschriftung ist eine Regel.

Untersuchen Sie die Funktionsweise des NKA für die Wörter \(w_1 = aabb\), \(w_2 = baba\) und \(w_3 = aba\).

Hilfe 1 (Notation):
Notieren Sie nach jedem Schritt Zustand und Kellerinhalt, z. B. \(q_1\,[\#a]\) (oben rechts).
Hilfe 2 (Ende):
Ist das Wort gelesen, prüfen Sie, ob noch ein ε-Übergang möglich ist und ob der Automat danach in einem Endzustand ist.

Beschreiben Sie die Sprache, welche vom NKA akzeptiert wird.

Hilfe 1 (Keller deuten):
Was steht im Keller, wenn mehr a als b gelesen wurden, was im umgekehrten Fall? Wann kann der Automat in den Endzustand wechseln?
Aufgabe 2: Klammerausdrücke prüfen (Einzelarbeit)

Ein gängiges Problem beim Programmieren ist, dass Ausdrücke mit mehreren Klammerpaaren hinsichtlich ihrer Korrektheit geprüft werden müssen. Dies übernimmt unter anderem ein sogenannter Parser, verkürzt gesagt ein Programm, das Code auf seine syntaktische (grammatische) Korrektheit prüft. Wir beschränken uns zunächst auf Klammerausdrücke ohne nebeneinanderliegende Klammerpaare, also z. B. {{{}}}, aber nicht {{}{}}.

Im Java-Code if (b == true) { a = a + 1; fehlt die schließende Klammer. Man kann annehmen, dass sich der Parser ab der geöffneten Klammer gemerkt hat: „Es fehlt eine geschlossene Klammer.“ Korrekte Klammerausdrücke bis zur Tiefe 2 sind {} und {{}}. Nicht korrekt sind z. B. }{ oder }{}{ und {}}}. Modelliert man die Prüfung bis zur Tiefe 2 als DEA, ergibt sich der folgende Zustandsgraph:

Entwickeln Sie den Zustandsgraphen eines DEA, der Klammerpaare aus geschweiften Klammern bis zu einer Tiefe von 3 auf ihre Korrektheit überprüft.

Hilfe 1 (Tiefe merken):
Die Zustände merken sich, wie viele Klammern gerade offen sind: 0, 1, 2 oder 3.
Hilfe 2 (Fehlerfälle):
Eine schließende Klammer bei Tiefe 0 und eine vierte öffnende Klammer führen in den Fehlerzustand.

Erläutern Sie, wie sich der Zustandsgraph aus a) ändert, wenn die maximale Tiefe auf 4 erhöht wird.

Hilfe 1 (Vergleich):
Was kommt hinzu, wenn eine Klammer mehr offen sein darf?

Erläutern Sie, dass es keinen endlichen Automaten geben kann, der einen einfach geschachtelten Klammerausdruck mit beliebiger Tiefe auf seine Korrektheit prüfen kann.

Hilfe 1 (Schluss ziehen):
Jede weitere Tiefe braucht einen weiteren Zustand. Wie viele Zustände bräuchte man für jede beliebige Tiefe – und wie viele hat ein endlicher Automat?

Entwickeln Sie einen NKA in Form eines Zustandsgraphen, der einfach geschachtelte Klammerausdrücke beliebiger Tiefe überprüfen kann.

Hilfe 1 (Keller als Zähler):
Legen Sie für jede öffnende Klammer ein Zeichen in den Keller und entfernen Sie für jede schließende Klammer eines.
Hilfe 2 (Ende):
Akzeptiert wird, wenn am Ende nur noch # im Keller liegt. Dazu dient ein ε-Übergang in den Endzustand.
Aufgabe 3: Lösungsvorschläge beurteilen (Gruppenarbeit)

Diese Aufgabe wurde von Jana Tholen (Osnabrück, 2025) erstellt und verändert.

Für die Sprache \(L = \{w \mid w = a^n b c^n;\ n \in \mathbb{N}_0\}\) soll ein NKA entworfen werden, der Akzeptor der Sprache ist. \(\mathbb{N}_0\) bezeichnet die natürlichen Zahlen einschließlich der 0. Hierfür gibt es drei Vorschläge:

Beurteilen Sie die Lösungsvorschläge und korrigieren Sie gegebenenfalls Fehler, sodass die Automaten korrekt arbeiten.

Hilfe 1 (Testwörter):
Testen Sie jeden Vorschlag mit b, abc, aabcc und mit fehlerhaften Wörtern wie aabc, abcc oder ac.
Hilfe 2 (Typische Fehler):
Achten Sie darauf, ob am Ende geprüft wird, dass nur noch # im Keller liegt, und ob das Wort b (n = 0) akzeptiert wird.

Verändern Sie eine korrekte Lösung so, dass der Automat für \(n \in \mathbb{N}\) (also ohne die 0) korrekt funktioniert.

Hilfe 1 (Ansatz):
Der Automat muss mindestens ein a lesen, bevor b erlaubt ist. Welcher Übergang erlaubt bisher ein b ohne vorheriges a?
Aufgabe 4: Geschachtelte Klammerausdrücke (Partnerarbeit)

Nun soll ein Klammerausdruck auch mit geschachtelten Klammern auf seine Korrektheit überprüft werden. Korrekte Ausdrücke dieser Art sind z. B. {{}}{}, {{}{}} oder {}{}. Auch ein leerer Klammerausdruck wird akzeptiert.

Entwickeln Sie einen NKA als Zustandsgraph und in formaler Notation, welcher genau diese Klammerausdrücke akzeptiert.

Hilfe 1 (Vergleich mit Aufgabe 2 d)):
Der Unterschied: Nach einer schließenden Klammer darf wieder eine öffnende kommen.
Hilfe 2 (Ein Zustand genügt fast):
Öffnen und Schließen können im selben Zustand stattfinden. Ein ε-Übergang mit # oben führt in den Endzustand.
Aufgabe 5: DEA oder NKA? (Partnerarbeit)

Untersuchen Sie in jedem Aufgabenteil, ob die Situation durch einen DEA realisiert werden kann. Entwerfen Sie dann einen geeigneten DEA oder gegebenenfalls NKA als Zustandsgraph und mit formaler Definition (5-Tupel bzw. 7-Tupel).

Ein Automat soll genau die folgenden Eingaben akzeptieren: Das Eingabealphabet sind die Ziffern 0, …, 9. Die Ziffer 1 kommt genau doppelt so häufig vor wie die Ziffer 0. Nachdem die erste 1 im Wort auftaucht, dürfen keine Nullen mehr kommen.

Hilfe 1 (Merken):
Muss sich der Automat eine unbegrenzte Anzahl merken? Dann reicht ein DEA nicht.
Hilfe 2 (Keller):
Legen Sie für jede 0 zwei Zeichen in den Keller und entfernen Sie für jede 1 eines. Andere Ziffern ändern den Keller nicht.

Die Eingabewörter (alle Kleinbuchstaben sind möglich) müssen mit „abc“ beginnen und auf „xyz“ enden.

Hilfe 1 (Merken):
Hier muss sich der Automat nur merken, wie viel von abc bzw. xyz schon gelesen wurde. Das sind endlich viele Möglichkeiten.
Aufgabe 6: Ein Akzeptor für \(a^n b^m c^{n+m} d\) (Partnerarbeit)

Ein Automat soll Akzeptor der Sprache \(L = \{w \mid w = a^n b^m c^{n+m} d;\ n, m \in \mathbb{N}\}\) sein.

Erläutern Sie, weshalb ein DEA nicht geeignet ist.

Hilfe 1 (Merken):
Was müsste sich ein DEA merken, um die Anzahl der c zu prüfen? Ist diese Anzahl begrenzt?

Entwerfen Sie einen NKA in Form eines Zustandsgraphen, der Akzeptor der Sprache \(L\) ist.

Hilfe 1 (Keller füllen):
Legen Sie für jedes a und jedes b dasselbe Zeichen in den Keller.
Hilfe 2 (Keller leeren):
Entfernen Sie für jedes c ein Zeichen. Am Ende muss d gelesen werden und nur noch # im Keller liegen.
Aufgabe 7: Die Rangieranlage (Partnerarbeit)

Ein Zug aus \(n\) unterscheidbaren Wagen \(\{w_1, \dots, w_n\}\) befindet sich wie abgebildet auf Gleis \(G_1\) einer Rangieranlage. \(G_2\) und \(G_3\) sind leer. Die Gleisanlage ist mit einem Automaten verbunden, der für die angegebenen Eingaben die zugeordneten Aktionen ausführt.

G3G1G2 (Rangiergleis)w1w2…wn← Ausfahrt← Einfahrt
EingabeAktion
1Falls \(G_1\) nicht leer: rangiere den ersten Wagen von \(G_1\) nach \(G_2\); sonst Fehler
2Falls \(G_2\) nicht leer: rangiere den ersten Wagen von \(G_2\) nach \(G_3\); sonst Fehler

Interpretieren Sie die Eingabefolge 112122 für einen Zug mit mindestens drei Wagen und geben Sie die Reihenfolge der Wagen (von links nach rechts) auf \(G_3\) an.

Hilfe 1 (Nachspielen):
Notieren Sie nach jeder Eingabe, welche Wagen auf \(G_1\), \(G_2\) und \(G_3\) stehen. \(G_2\) funktioniert wie ein Stapel.

Geben Sie die Eingabefolge an, die bei einem Zug mit 4 Wagen die beiden mittleren Wagen tauscht.

Hilfe 1 (Stapel nutzen):
Auf \(G_2\) kehrt sich die Reihenfolge um. Welche zwei Wagen müssen gleichzeitig auf \(G_2\) stehen?

Geben Sie eine mindestens dreielementige Eingabefolge an, die in einen Fehlerzustand führt, und begründen Sie Ihre Wahl.

Hilfe 1 (Fehler):
Ein Fehler entsteht, wenn von einem leeren Gleis rangiert werden soll. Wann ist \(G_2\) leer?

Die Sprache \(L\) sei die Menge aller Eingabefolgen, die zu keinem Fehlerzustand führen und einen Zug beliebiger Länge vollständig von \(G_1\) nach \(G_3\) rangieren. Beschreiben Sie \(L\) und definieren Sie einen geeigneten Automaten, der \(L\) akzeptiert.

Hilfe 1 (Bedingungen):
Zu jedem Zeitpunkt dürfen nicht mehr Zweien als Einsen gelesen sein, und am Ende muss die Anzahl gleich sein. Woran erinnert das?
Hilfe 2 (Automat):
Ein Kellerautomat kann \(G_2\) direkt nachbilden: 1 legt ein Zeichen ab, 2 entfernt eines.
Aufgabe 8: Der Mixgetränkeautomat (Partnerarbeit)

Aus Informatik 2, Schöningh Verlag (abgewandelt)

An einer Saftbar soll ein Mixgetränkeautomat dem Personal zu Stoßzeiten helfen. Der Automat kann nur eine begrenzte Zahl an Getränken herstellen und die folgenden Aktionen ausführen: c: Cola hinzufügen, w: Waldmeistersirup hinzufügen, m: mit dem Mixlöffel rühren, s: mit dem Shaker schütteln. Die Regeln zum Mixen sind:

  1. Alle Zutaten werden auf jeden Fall in den Shaker gegeben, aber nicht unbedingt geschüttelt.
  2. Cola darf niemals alleine mit dem Mixlöffel gerührt werden.
  3. Waldmeistersirup kann nicht pur angeboten werden.
  4. Es wird entweder geschüttelt oder gerührt.
  5. Das Getränk muss in einem Glas mit Strohhalm serviert werden.
  6. Unsinnige Aktionen, wie Rühren ohne Zutaten oder mehrfaches Rühren oder Mixen, gibt es nicht.
  7. Das Füllen ins Glas soll unbeachtet bleiben.
  8. Cola oder Waldmeistersirup dürfen jeweils maximal einmal ins Glas gefüllt werden.

Geben Sie je zwei strukturell verschiedene gültige und ungültige Eingaben für den Mixautomaten an. Entwerfen Sie einen DEA als Zustandsgraph und in formaler Definition, der den Mixautomaten darstellt.

Hilfe 1 (Relevante Regeln):
Streichen Sie zuerst die Regeln, die mit dem Automaten nichts zu tun haben (z. B. das Glas).
Hilfe 2 (Zustände):
Die Zustände merken sich, welche Zutaten schon im Shaker sind und ob schon gerührt oder geschüttelt wurde.

Der Betreiber der Saftbar entscheidet, die Getränke in Flaschen abzufüllen und zu verkaufen. Die Getränke werden nun in einem deutlich größeren Mixbehälter von einem großen Rührer gemixt und die Regeln wurden verändert: a steht für Abfüllen, r für Rühren, die anderen Eingaben sind wie bisher. Die Abbildung zeigt den Zustandsgraphen eines neuen DEA.

  • Geben Sie ein Wort maximaler Länge an, das genau ein r enthält und akzeptiert wird. Begründen Sie, warum es kein längeres Wort geben kann.
  • Analysieren Sie, ob der gegebene Automat minimal ist.
  • Analysieren Sie, welche Mischverhältnisse zwischen den Zutaten zulässig sind.
Hilfe 1 (Längstes Wort):
Suchen Sie einen Weg vom Start zum Endzustand, der genau eine r-Kante benutzt und dabei möglichst viele andere Kanten.
Hilfe 2 (Minimalität):
Zwei Zustände dürfen nur zusammengelegt werden, wenn von beiden aus genau dieselben Restwörter akzeptiert werden.

Eine clevere Mitarbeiterin hat den Mixautomaten umprogrammiert. Zulässige Wörter sind nun nur noch Palindrome aus Cola und Waldmeistersirup, die zu Beginn und am Ende aus w's und dazwischen aus c's bestehen. In der Wortmitte muss ein x stehen. Am Ende wird nur noch umgerührt und abgefüllt.

Geben Sie je ein zulässiges und ein unzulässiges Wort an. Entwerfen Sie einen NKA in Form eines Zustandsgraphen, der die neue Sprache akzeptiert.

Hilfe 1 (Erste Hälfte):
Legen Sie alle Zeichen vor dem x in den Keller.
Hilfe 2 (Zweite Hälfte):
Nach dem x muss jedes gelesene Zeichen mit dem obersten Kellerzeichen übereinstimmen und wird entfernt. Danach folgen noch r und a.
Aufgabe 9: Ein Automat muss raten (Partnerarbeit)

Gegeben ist die Sprache \(L = \{a^n b^m \mid n \geq 1 \text{ und } m = n \text{ oder } m = 2n\}\). Zu \(L\) gehören z. B. ab, abb, aabb und aabbbb, nicht aber aabbb. Der folgende Kellerautomat akzeptiert \(L\). Im Zustand \(q_0\) hat er für dieselbe Situation (oben #, kein Eingabezeichen) zwei Übergänge.

Geben Sie für die Wörter aabb, aabbbb und aabbb jeweils beide Rechenwege an (Zustand und Kellerinhalt nach jedem Schritt). Entscheiden Sie jeweils, ob das Wort akzeptiert wird.

Hilfe 1 (Erster Schritt):
Der Automat liest im ersten Schritt kein Zeichen. Er wechselt über einen \(\varepsilon\)-Übergang entweder nach \(q_1\) oder nach \(q_3\). Verfolgen Sie beide Möglichkeiten getrennt.
Hilfe 2 (Kellerinhalt):
Im oberen Zweig (\(q_1\)) wird für jedes a ein A abgelegt, im unteren Zweig (\(q_3\)) zwei. Jedes b entfernt genau ein A.
Hilfe 3 (Ende des Wortes):
Ein Rechenweg endet erfolgreich, wenn das ganze Wort gelesen ist und der Automat danach (eventuell über einen \(\varepsilon\)-Übergang) in \(q_5\) ist.

Erläutern Sie, an welcher Stelle der Automat nichtdeterministisch arbeitet und warum er sich dort noch nicht sicher richtig entscheiden kann.

Hilfe 1 (Wo gibt es zwei Möglichkeiten?):
Suchen Sie die Situation, in der zwei Übergänge mit demselben obersten Kellerzeichen und demselben Eingabezeichen (hier \(\varepsilon\)) passen.
Hilfe 2 (Welche Information fehlt?):
Ob m = n oder m = 2n gilt, entscheidet sich erst an der Anzahl der b. Wann liest der Automat die b?

Begründen Sie mit der Akzeptanzbedingung, warum aabb akzeptiert wird, obwohl einer der beiden Rechenwege nicht in einem Endzustand endet.

Hilfe 1 (Akzeptanzbedingung):
Lesen Sie im Kasten „Nichtdeterminismus“ nach: Wie viele erfolgreiche Rechenwege braucht ein Wort?
🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Sie haben alle Aufgaben bearbeitet und abgehakt. Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.

Formale Sprachen

eA

Reguläre Sprachen

Der Imbissroboter aus dem Aquapark (Material Jahrgang 10) soll nun Bestellungen für verschiedene Gerichte und Komponenten aufnehmen können. Dazu muss er prüfen, ob diese korrekt eingegeben wurden.

Aufgabe (Austauschphase → Gespräch mit der Lerngruppe): (entworfen in Zusammenarbeit mit Jana Tholen, Osnabrück 2025)
a) Betrachten Sie die Abbildung und diskutieren Sie, welche Speisen beim Imbissroboter bestellt werden können. Der Roboter startet bei „Start“, kann nur in Pfeilrichtung (von oben nach unten durch die Kästen) und nicht rückwärts gehen. Ein lilafarbenes Kästchen mit Großbuchstaben verweist auf das gleichnamige Diagramm. Am Ende eines Diagramms ist eine Bestellung aufgenommen.
b) Entscheiden Sie, für welche der Gerichte keine, mindestens eine, maximal eine, genau eine, mindestens zwei, maximal zwei oder genau zwei weitere Komponenten bestellt werden können bzw. müssen.
c) Verändern Sie das Diagramm durch weitere Speisen/Getränke so, dass die Fälle, die in b) nicht auftauchen, im Diagramm vorkommen.
b) keine Komponente → Pizzaschnecke; maximal eine → Burger_vegan; genau eine → Pommes; genau zwei → Salat.
c) Eine Erweiterung für „maximal zwei“ könnte z. B. ein weiterer Burger sein: Start → … | Burger E, E → ε | Bacon | Käse | Bacon F | Käse F, F → ε | Bacon | Käse.

Fazit: Die Abbildung, auch Syntaxdiagramm genannt, zeigt die Produktionsregeln aller bestellbaren Speisen. Beim Start kann man sich entscheiden, ob man mit Pizzaschnecke, Pommes, Burger_vegan oder Salat startet. Je nach Speise ist es möglich, weitere Komponenten hinzuzufügen. Dies kann man auch mit einem Ableitungsbaum darstellen:

Zur Bildung eines Wortes startet man immer mit einem Startsymbol S, einer Art Variable, die man als Nichtterminal bezeichnet. Für unsere Speisen kann S direkt durch ein Zeichen der Sprache, ein Terminal, ersetzt werden (nur Pizzaschnecke steht allein) oder durch Pommes, Burger_vegan oder Salat zusammen mit einem weiteren Nichtterminal A, B oder C rechts davon. Anschließend muss z. B. das Nichtterminal A durch Mayonnaise oder Ketchup ersetzt werden.

Nun können wir die Grammatik der Sprache der Speisen als 4-Tupel \(G = (N, T, S, P)\) angeben. Die Grammatik beschreibt, wie die Wörter erzeugt werden; die Sprache \(L(G)\) ist die Menge aller Wörter, die so erzeugt werden können.

DefinitionSpeisen
\(N\)Nicht leere, endliche Menge der Nichtterminale (Hilfssymbole) für die Erzeugung von Wörtern.\(N = \{S, A, B, C, D\}\)
\(T\)Nicht leere, endliche Menge der Terminale. Dies sind die Buchstaben oder Silben, die in Wörtern der Sprache vorkommen. \(N\) und \(T\) haben keine gemeinsamen Elemente.\(T = \{\)Pizzaschnecke, Pommes, Burger_vegan, Salat, Mayonnaise, Ketchup, Jalapenos, Avocado, Tofu, Garnelen, Putenbrust\(\}\)
\(S\)Startsymbol. Eines der Nichtterminale muss als Startsymbol definiert werden. Damit startet die Bildung aller Wörter der Sprache.S
\(P\)Produktionsregeln. Dies sind alle Erzeugungsregeln der Wörter. Das Zeichen \(\varepsilon\) steht für das leere Wort und ist kein Terminal: Die Regel B → ε bedeutet, dass B durch nichts ersetzt wird.S → Pizzaschnecke | Pommes A | Burger_vegan B | Salat C
A → Mayonnaise | Ketchup
B → ε | Avocado | Jalapenos
C → Tofu D | Garnelen D | Putenbrust D
D → Tofu | Garnelen | Putenbrust
Aufgabe (Austauschphase → Gespräch mit der Lerngruppe):
a) Analysieren Sie die Produktionsregeln und erläutern Sie, wie diese zu verstehen sind.
b) Vergleichen Sie die Definition einer regulären Sprache mit anderen bekannten Informatiksystemen, die eine ähnliche Darstellung haben.
a) Der senkrechte Strich | steht für eine Auswahl zwischen Alternativen. Steht ein Großbuchstabe (Nichtterminal) hinter einem Terminal, muss man anschließend bei der Regel dieses Nichtterminals weitermachen. Ein Wort kann enden, wenn ein einzelnes Terminal folgt oder ein Nichtterminal durch ε ersetzt wird (B → ε).
b) Es gibt deutliche Gemeinsamkeiten mit einem DEA: Die Nichtterminale entsprechen den Zuständen, die Terminale den Eingabezeichen, das Startsymbol dem Startzustand und die Produktionsregeln den Zustandsübergängen.

Unser Beispiel der Speisen ist eine reguläre Sprache. Eine Sprache heißt regulär, wenn es eine reguläre Grammatik gibt, die sie erzeugt. Eine reguläre Grammatik ist entweder rechtsregulär oder linksregulär. Üblich ist die rechtsreguläre Form, die wir im Folgenden verwenden.

Eine Grammatik \(G = (N, T, S, P)\) heißt linksregulär bzw. rechtsregulär, wenn alle Produktionsregeln die folgende Form haben:
linksregulärrechtsregulär
Ein Nichtterminal → ein Terminal (Bsp.: A → +)
oder
Ein Nichtterminal → ein Nichtterminal und ein Terminal (Bsp.: S → A Mayonnaise)
oder
Ein Nichtterminal → ε (Bsp.: B → ε)
Ein Nichtterminal → ein Terminal (Bsp.: A → +)
oder
Ein Nichtterminal → ein Terminal und ein Nichtterminal (Bsp.: S → Pommes A)
oder
Ein Nichtterminal → ε (Bsp.: B → ε)
Die Wörter werden von rechts nach links aufgebaut:
S → A Mayonnaise → Pommes Mayonnaise
Die Wörter werden von links nach rechts aufgebaut:
S → Pommes A → Pommes Mayonnaise

Aufgaben zu regulären Sprachen

Ihr Bearbeitungsfortschritt:0%
Aufgabe 1: Schulnoten, Uhrzeiten, Kennzeichen und Terme (Partnerarbeit)
syntaktisch korrektsyntaktisch nicht korrekt
Schulnoten1-, 2+, 5-, 6+1+, 6-, 3+-, -4
Uhrzeit10:05, 23:54, 02:3110::05, 23:5544, 06:89
AutokennzeichenOS-AB-1234, HH-CD-23, M-E-1OS AB 1234, HHCD 23, M 1-E
Terme(1+2)*(5-4), 3*(15-4), 9-(2+4))1+2)*(5-4), 3()*(15-), 9+-2+4)

Geben Sie für die Schulnoten, die Uhrzeit und die Autokennzeichen die formalen Definitionen der Sprachen an. Bei den Autokennzeichen gilt: 1 bis 3 Buchstaben für den Zulassungsort, dann ein -, gefolgt von 1 bis 2 Buchstaben, ein - und 1 bis 4 Ziffern.

Hilfe 1 (Schema):
Geben Sie jeweils eine Grammatik \(G = (N, T, S, P)\) an. Beginnen Sie mit den Terminalen: Welche Zeichen kommen vor?
Hilfe 2 (Rechtsregulär arbeiten):
Bauen Sie die Wörter von links nach rechts auf. Jedes Nichtterminal steht für „was noch fehlt“, z. B. bei der Uhrzeit „zweite Ziffer der Stunde“.
Hilfe 3 (Sonderfälle):
Schulnoten: 1+ und 6- gibt es nicht. Uhrzeit: Nach einer 2 als erster Ziffer sind nur 0 bis 3 möglich.

Entscheiden Sie, ob es sich bei diesen Beispielen um reguläre Sprachen handelt.

Hilfe 1 (Kriterium):
Lässt sich eine reguläre Grammatik (oder ein DEA) angeben? Problematisch sind Strukturen, bei denen man beliebig viel zählen muss, z. B. geschachtelte Klammern.

Für Terme mit Klammerpaaren der maximalen Tiefe 1 (keine geschachtelten Klammern wie (())) und nur +, - oder * ist der folgende Vorschlag gegeben:

N = {S, A, B, C, D, E, F}, T = {0-9, 1-9, +, -, *, (, )}, Startsymbol S
S → 0-9 | 0-9 A | 1-9 B | ( C
A → + S | - S | * S
B → 0-9 | 0-9 B | 0-9 S
C → 0-9 F | 0-9 D | 1-9 E
D → + C | - C | * C
E → 0-9 F | 0-9 E | 0-9 C
F → ) | ) A

Beurteilen Sie den Vorschlag und diskutieren Sie, welche Änderungen notwendig werden, wenn 1. ein weiteres Klammerpaar erlaubt ist, 2. die Division hinzukommt, 3. eine beliebige Klammertiefe erlaubt ist.

Hilfe 1 (Testen):
Leiten Sie einige korrekte Terme ab und versuchen Sie, auch fehlerhafte Terme abzuleiten. Werden alle Terme erzeugt, und nur diese?
Hilfe 2 (Klammertiefe):
Was müsste die Grammatik sich merken, wenn beliebig viele Klammern geschachtelt werden dürfen?
Aufgabe 2: Syntaxdiagramme (Einzelarbeit)

Erstellen Sie je ein Syntaxdiagramm für die formale Sprache

a) \(L_{Klasse}\) mit den syntaktisch korrekten Wörtern wie 5a, 8c oder 11e. Die Klassen 5–10 sind maximal vierzügig, der Jahrgang 11 ist maximal sechszügig.
b) \(L_{Uhr}\) der Uhrzeiten aus Aufgabe 1.
c) \(L_{\mathbb{N}}\), die Sprache der natürlichen Zahlen.
d) \(L_{\mathbb{Z}}\), die Sprache der ganzen Zahlen.

Hilfe 1 (Aufbau):
Ein Syntaxdiagramm liest man in Pfeilrichtung. Verzweigungen sind Alternativen, Rückwärtspfeile Wiederholungen.
Hilfe 2 (Klassen):
Trennen Sie die Jahrgänge 5–10 (Buchstaben a–d) und 11 (Buchstaben a–f) in zwei Zweige.
Hilfe 3 (Zahlen):
Natürliche Zahlen beginnen nicht mit 0 (außer der 0 selbst). Für die ganzen Zahlen kommt ein optionales Minuszeichen vor einer Zahl ungleich 0 hinzu.
Aufgabe 3: Fahrzeuge im ÖPNV (Partnerarbeit)

In einer Stadt gibt es die U-Bahnlinien U74 bis U79, die S-Bahnlinien S1 bis S6 und die Buslinien 701 bis 716. Erstellen Sie eine reguläre Grammatik und ein Syntaxdiagramm der Sprache \(L_{ÖPNV}\), die aus den Bezeichnungen aller Fahrzeuge besteht.

Hilfe 1 (Drei Fälle):
Unterscheiden Sie im Startsymbol drei Zweige: U-Bahn, S-Bahn und Bus.
Hilfe 2 (Ziffern):
Bei U74 bis U79 ist die erste Ziffer immer 7, die zweite 4 bis 9. Bei 701 bis 716 lohnt sich eine Fallunterscheidung nach der zweiten Ziffer.
Aufgabe 4: Regulär oder nicht? (Partnerarbeit)

Erläutern Sie, weshalb die Grammatik \(G = (\{S, N\}, \{0, 1\}, S, P)\) mit den Produktionsregeln S → 1 | 1 N und N → 0 | N 0 nicht regulär ist.

Hilfe 1 (Regeln prüfen):
Vergleichen Sie jede Regel mit den erlaubten Formen. Steht ein Nichtterminal links oder rechts vom Terminal? Sind beide Formen gemischt?

Zeigen Sie, dass die von dieser Grammatik erzeugte Sprache trotzdem regulär ist.

Hilfe 1 (Sprache bestimmen):
Schreiben Sie einige Wörter auf, die die Grammatik erzeugt. Wie sehen sie aus?
Hilfe 2 (Nachweis):
Geben Sie eine rechtsreguläre Grammatik oder einen DEA für dieselbe Sprache an.
Aufgabe 5: Die lal-Sprache (Einzelarbeit)

In der lal-Sprache \(L_{lal}\) können nur die Silben la, le und lu in einem Wort vorkommen. Diese können beliebig kombiniert werden, aber am Ende jedes Wortes muss lu stehen. Ein Wort besteht aus genau drei Silben. Erstellen Sie eine reguläre Grammatik für \(L_{lal}\).

Hilfe 1 (Silben als Terminale):
Nehmen Sie la, le und lu als Terminale. Jedes Nichtterminal steht für die Anzahl der noch fehlenden Silben.
Aufgabe 6: Hawaiianisch (Partnerarbeit)

In der hawaiianischen Sprache gibt es nur die Vokale a, e, i, o, u und die Konsonanten h, k, l, m, n, p, w. Alle Wörter sind nach der folgenden Regel aufgebaut: 1. Einem Vokal können beliebig viele Vokale folgen. 2. Nach einem Konsonanten muss ein Vokal folgen, es darf kein weiterer Konsonant stehen. Beispiele: „kumu“ (Lehrer), „wikiwiki“ (schnell bzw. eifrig), „hula“ (Sammelbegriff für hawaiianische Tänze). Erstellen Sie eine reguläre Grammatik für die hawaiianische Sprache.

Hilfe 1 (Zwei Situationen):
Unterscheiden Sie mit zwei Nichtterminalen, ob zuletzt ein Vokal oder ein Konsonant stand.
Hilfe 2 (Wortende):
Ein Wort darf nur nach einem Vokal enden. Wo braucht die Grammatik deshalb eine Regel mit einem einzelnen Terminal?
Aufgabe 7: Die Kaffeemaschine (Partnerarbeit)

Eine Kaffeemaschine wird mit einer Befehlsfolge aus k (Kaffee), m (Milch) und z (Zucker) programmiert. Ein Latte Macchiato wird z. B. mit kkmmmzz programmiert, ein Espresso mit kkkk. Die Reihenfolge ist beliebig und theoretisch unendlich lang (mkmkzmz ist also auch ein Latte Macchiato). Jede Mischung muss aber mindestens einmal Kaffee enthalten.

Geben Sie eine reguläre Grammatik an, die richtige Kaffeemaschinenprogramme erzeugt.

Hilfe 1 (Regeln sammeln):
Notieren Sie zuerst, welche Zutat auf welche folgen darf und womit ein Programm enden darf.
Hilfe 2 (Nichtterminale):
Ein Nichtterminal je Situation, z. B. „zuletzt Kaffee“, „zuletzt Milch“.

Jetzt sollen mehrere Kaffees hintereinander eingegeben werden können. Anfang und Ende eines Kaffees werden durch Klammern markiert, z. B. (mkmkzmz)(kkkk). Bestandteile außerhalb von Klammerpaaren werden ebenfalls als eigener Kaffee interpretiert: kk(kmzzm)mkzzkz(kmmmm) liefert die vier Kaffees kk, kmzzm, mkzzkz und kmmmm. Geben Sie eine Grammatik für diese Programmiersprache an. Sie soll nur gültige Wörter erzeugen, nicht die Funktion des Automaten simulieren.

Hilfe 1 (Wiederholen):
Nach dem Ende eines Kaffees muss die Grammatik wieder zum Anfang zurückkehren können.
Hilfe 2 (Klammern):
Die Klammern sind nicht geschachtelt. Reicht deshalb eine reguläre Grammatik?
🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Sie haben alle Aufgaben bearbeitet und abgehakt. Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.

Reguläre Sprachen und DEA

Wir betrachten noch einmal die Sprache \(L_{Schulnoten}\). Sie wird von der Grammatik \(G = (N, T, S, P)\) mit

N = {S, A, B, C}, T = {1, 2, 3, 4, 5, 6, +, -}, Startsymbol S
S → 1 | 2 | 3 | 4 | 5 | 6 | 1 A | 2 B | 3 B | 4 B | 5 B | 6 C
A → -
B → + | -
C → +

erzeugt.

Aufgabe (Partnerarbeit): Einen Zusammenhang zwischen Sprachen und Automaten haben wir schon vermutet. Entwerfen Sie den Zustandsgraphen eines DEA, der Akzeptor der Sprache \(L_{Schulnoten}\) ist. Hinweis: Das Startsymbol kann als Startzustand betrachtet werden.

Das Erstellen eines Wortes nach dieser Grammatik ist sehr ähnlich zum Abarbeiten einer Eingabe durch einen DEA. Das Startsymbol interpretieren wir als Startzustand, die Terminale als Eingabealphabet und die Nichtterminale als weitere Zustände. Anhand der Produktionsregeln konstruiert man die Zustandsübergänge.

Nach einer 1, 2, 3, 4, 5 oder 6 ist bereits eine korrekte Eingabe erreicht. Diesen Zeichen kann aber noch ein weiteres, nicht immer gleiches Zeichen folgen: für 1 ein anderes als für 2–5 und noch ein drittes für 6. Daher gibt es für jedes dieser Nichtterminale A, B, C einen Zustand. Da einzelne Noten bereits fertige Wörter sind, sind \(q_1\), \(q_3\) und \(q_4\) Endzustände:

Mit den Produktionsregeln A → -, B → + | - und C → + geht es weiter:

Zu jedem Zustandsübergang des DEA gibt es ein Äquivalent in den Produktionsregeln und umgekehrt. Allgemein gibt es zu jeder regulären Sprache einen DEA, der genau diese Sprache akzeptiert, und zu jedem DEA eine reguläre Grammatik, die die vom DEA akzeptierte Sprache bildet. Ist fraglich, ob eine Grammatik regulär ist, kann man also versuchen, einen DEA zu entwerfen, der die Sprache der Grammatik akzeptiert.

Eine Sprache ist genau dann regulär, wenn es eine reguläre Grammatik gibt, die diese Sprache erzeugt.
Äquivalent hierzu ist:
Eine Sprache ist genau dann regulär, wenn es einen DEA gibt, der Akzeptor dieser Sprache ist.

Aufgaben zu regulären Sprachen und DEA

Ihr Bearbeitungsfortschritt:0%
Aufgabe 1: Von der Grammatik zum DEA (Einzelarbeit)

Entwickeln Sie einen DEA in Form eines Zustandsgraphen für die lal-Sprache (siehe Aufgaben zu regulären Sprachen).

Hilfe 1 (Übersetzen):
Aus jedem Nichtterminal wird ein Zustand, aus jeder Regel A → x B eine Kante von A nach B mit der Beschriftung x.

Entwickeln Sie einen DEA in Form eines Zustandsgraphen für die Sprache der Nummernschilder (siehe Aufgaben zu regulären Sprachen).

Hilfe 1 (Übersetzen):
Nutzen Sie Ihre Grammatik aus Aufgabe 1 a): Nichtterminale werden Zustände, Terminale Kantenbeschriftungen. Fassen Sie Buchstaben und Ziffern zu je einer Beschriftung zusammen.

Entwickeln Sie einen DEA in Form eines Zustandsgraphen für die hawaiianische Sprache (siehe Aufgaben zu regulären Sprachen).

Hilfe 1 (Zwei Zustände):
Ein Zustand für „zuletzt Vokal“ (Endzustand) und einer für „zuletzt Konsonant“ genügen fast.
Aufgabe 2: Boolesche Ausdrücke (Partnerarbeit)

Gegeben ist der folgende Automat zum Erkennen boolescher Ausdrücke mit dem Eingabealphabet {a, b, &, |, !}. Alle nicht eingezeichneten Pfeile führen in einen Fehlerzustand.

Beschreiben Sie, welche Sprache der DEA akzeptiert.

Hilfe 1 (Wörter testen):
Lesen Sie einige akzeptierte Wörter aus dem Graphen ab. Wo darf ! stehen, wo & und |?

Setzen Sie den Automaten in eine reguläre Grammatik um.

Hilfe 1 (Übersetzen):
Jeder Zustand wird ein Nichtterminal, jede Kante von A nach B mit x eine Regel A → x B. Führt eine Kante in einen Endzustand, kommt zusätzlich A → x hinzu.
Aufgabe 3: Römische Zahlen (Partnerarbeit)

Entwickeln Sie einen endlichen Automaten, der genau die römischen Zahlen von 1 bis 10 akzeptiert.

Hilfe 1 (Liste):
Schreiben Sie alle zehn Zahlwörter auf: I, II, III, IV, V, VI, VII, VIII, IX, X. Gleiche Anfänge teilen sich Zustände.

Setzen Sie Ihren Automaten in eine reguläre Grammatik um.

Hilfe 1 (Übersetzen):
Zustände werden Nichtterminale, Kanten werden Regeln A → x B, Kanten in Endzustände zusätzlich A → x.

Erweitern Sie beide Modelle so, dass die römischen Zahlen von 1 bis 39 die Sprache bilden.

Hilfe 1 (Aufbau):
Die Zahlen bis 39 bestehen aus bis zu drei X und danach einer Zahl von 1 bis 9 oder nichts. Setzen Sie vor Ihren Automaten aus a) einen Teil für die X.
Aufgabe 4: Die Sprache \(a^n b^n\) (Partnerarbeit)

Wir betrachten die Sprache \(L = \{a^n b^n \mid n \in \mathbb{N}_0\}\), also alle Wörter, in denen auf eine Folge von a gleich viele b folgen. Das leere Wort ist erlaubt.

Versuchen Sie, eine reguläre Grammatik für diese Sprache zu entwickeln. Beginnen Sie mit dem leeren Wort (n = 0, Regel S → ε) und erweitern Sie die Grammatik schrittweise für n ≤ 1, n ≤ 2 und n ≤ 3. Beschreiben Sie, wie die Grammatik dabei wächst.

Hilfe 1 (Erster Schritt):
Für n ≤ 1 brauchen Sie S → ε | a A und A → b.
Hilfe 2 (Beobachten):
Notieren Sie nach jedem Schritt, wie viele Nichtterminale Sie brauchen. Was müssen sich die Nichtterminale merken?

Begründen Sie mit den Erkenntnissen aus a), dass es keinen DEA geben kann, der Akzeptor von \(L\) ist.

Hilfe 1 (Zusammenhang):
Eine Sprache ist genau dann regulär, wenn es einen DEA gibt, der sie akzeptiert. Wie viele Zustände bräuchte ein DEA, um sich jede Anzahl von a zu merken?
🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.

Chomsky-Hierarchie

Ergänzung

Die Chomsky-Hierarchie geht über das Kerncurriculum hinaus. Sie ordnet die bekannten Sprachklassen ein und ist als Ausblick gedacht.

Eine Computersprache ist analog zu natürlichen Sprachen wie Deutsch oder Englisch aufgebaut, nur muss in ihr alles eindeutig und korrekt geschrieben sein und darf keinen Interpretationsspielraum lassen. Es gibt verschiedene Sprachtypen mit steigendem Komplexitätsgrad der Grammatik. Der Sprachwissenschaftler Noam Chomsky hat 1956 eine Hierarchie aufgestellt, in der die formalen Sprachen nicht getrennt von den natürlichen Sprachen betrachtet, sondern hinsichtlich ihrer Wortbildungsregeln nach aufsteigender Komplexität geordnet werden.

Typ 0: rekursiv aufzählbar
Typ 1: kontextsensitiv
Typ 2: kontextfrei
Typ 3: regulär

Abb.: Hierarchie formaler Sprachen nach Noam Chomsky (1956)

Die bisher betrachteten Sprachen waren weitgehend regulär, also Typ-3-Sprachen. In der letzten Aufgabe haben wir festgestellt, dass selbst einfache Sprachen wie \(L = \{a^n b^n \mid n \in \mathbb{N}_0\}\) nicht regulär sind. Damit kann es keinen DEA geben, der Akzeptor dieser Sprache ist. Sie ist aber eine Typ-2-Sprache, also kontextfrei.

Kontextfreie Sprachen

Jetzt soll eine Grammatik für \(L_{a^n b^n} = \{a^n b^n \mid n \in \mathbb{N}_0\}\) entwickelt werden. Mit den Regeln einer regulären Grammatik kommt man nicht zurecht: Für n ≤ 2 hätte man vier Nichtterminale (S → ε | a A, A → b | a B, B → b C, C → b), und pro weiterem Paar „ab“ kommt für das zusätzliche a und das zusätzliche b je ein neues Nichtterminal hinzu. Könnte man direkt ein Paar „ab“ erzeugen, wäre das anders.

Aufgabe (Austauschphase → Lerngruppe): Diskutieren Sie, wie Sie alle Wörter der Sprache \(L_{a^n b^n}\) erzeugen können, wenn die Einschränkungen regulärer Grammatiken aufgehoben werden. Gehen Sie in dieser Reihenfolge vor: 1. Erstellen Sie eine Produktionsregel für das leere Wort. 2. Entwickeln Sie eine Produktionsregel für das Wort „ab“, 3. für „aabb“, 4. für „aaabbb“. 5. Entwickeln Sie eine vollständige Grammatik \(G = (N, T, S, P)\) mit \(L(G) = L_{a^n b^n}\).
Die Sprache \(L_{a^n b^n}\) wird durch die Grammatik mit \(N = \{S, A\}\), \(T = \{a, b\}\), Startsymbol S und S → ε | ab | a A b, A → ε | a A b definiert – oder kürzer mit \(N = \{S\}\) und S → ε | a S b. Das zweite Nichtterminal ist unnötig, da S selbst rekursiv das nächste Paar „a … b“ um das bisherige Wort legen kann.

Vergleicht man S → a S b mit den erlaubten Regeln einer regulären Grammatik (rechtsregulär: A → +B, linksregulär: A → B+), stellt man fest: Die Regel ist eine Mischung aus beiden. Die Grammatik ist weder links- noch rechtsregulär und damit keine reguläre Grammatik. Die Sprache ist also nicht regulär, sondern eine kontextfreie Sprache (Typ-2-Sprache).

Eine Grammatik \(G = (N, T, S, P)\) heißt kontextfrei, wenn alle Produktionsregeln die folgende Form haben:
Ein Nichtterminal → eine beliebige Kombination aus Terminal- und Nichtterminalsymbolen (Beispiel: A → + B - / C).

Aufgaben zu kontextfreien Sprachen

Ihr Bearbeitungsfortschritt:0%
Aufgabe 1: Immer wieder Klammern (Einzelarbeit)

Da eine korrekte Klammersetzung geprüft werden muss, wird jetzt eine Sprache entwickelt, die Klammerausdrücke produziert.

Erstellen Sie eine Grammatik zur Sprache \(L = \{\{^n\}^n \mid n \in \mathbb{N}_0\}\), die geschachtelte Klammerausdrücke wie {{}} oder {{{}}} erzeugt.

Hilfe 1 (Von außen nach innen):
Eine Regel der Form S → { S } erzeugt ein Klammerpaar außen und lässt innen Platz für weitere Klammern. Wie endet die Ableitung?

Erweitern Sie die Grammatik so, dass auch Klammerausdrücke wie {}{} oder {{}{}} möglich sind.

Hilfe 1 (Nebeneinander):
Ergänzen Sie eine Regel, mit der zwei korrekte Klammerausdrücke hintereinander stehen dürfen, z. B. S → S S.

Erläutern Sie mit Hilfe deterministisch endlicher Automaten, weshalb die Sprachen aus a) und b) nicht regulär sind.

Hilfe 1 (Merken):
Was müsste sich ein DEA beim Lesen der öffnenden Klammern merken? Ist diese Anzahl begrenzt?
Aufgabe 2: Eine Grammatik untersuchen (Partnerarbeit)

Gegeben ist die Grammatik G mit \(N = \{S, A, B, C, D\}\), \(T = \{a, b, c, d\}\), Startsymbol S und
S → A | a B | a C
A → B | C | c A d
B → S | B a
C → D | c
D → d | d D D

Geben Sie zwei strukturell verschiedene Wörter an, die mit dieser Grammatik gebildet werden können.

Hilfe 1 (Ableiten):
Beginnen Sie bei S und ersetzen Sie immer ein Nichtterminal, bis nur noch Terminale übrig sind. Wählen Sie für das zweite Wort einen anderen Weg (z. B. über c A d).

Erläutern Sie, weshalb die Grammatik nicht regulär ist.

Hilfe 1 (Regeln prüfen):
Suchen Sie Regeln, die weder rechtsregulär noch linksregulär sind, z. B. mit Terminalen auf beiden Seiten eines Nichtterminals.
Aufgabe 3: Rechenausdrücke (Partnerarbeit)

Die Sprache \(L_{RA}\) der einfachen Rechenausdrücke mit geschachtelten Klammern beinhaltet z. B. 1+2, 2*4, (5+7*(6+3)), (4+9)*3. Als Zahlen sind nur positive ganze Zahlen, als Rechenzeichen + und * erlaubt.

Erstellen Sie eine kontextfreie Grammatik der Sprache \(L_{RA}\).

Hilfe 1 (Bausteine):
Ein Ausdruck besteht aus Summanden, die durch + verknüpft sind, ein Summand aus Faktoren, die durch * verknüpft sind. Ein Faktor ist eine Zahl oder ein geklammerter Ausdruck.
Hilfe 2 (Zahlen):
Zahlen beginnen nicht mit 0. Ein eigenes Nichtterminal für die weiteren Ziffern hilft.

Erläutern Sie, weshalb \(L_{RA}\) nicht regulär ist.

Hilfe 1 (Klammern):
Klammern können beliebig tief geschachtelt werden. Vergleichen Sie mit Aufgabe 1 c).
Aufgabe 4: Sprachen und Grammatiken (Partnerarbeit)
\(L_1\)\(L_2\)\(L_3\)
N={S,A,B}, T={a,b}
S → a A
A → a A | B
B → b B | b
N={S,A}, T={a,b}
S → ab | ab S | ab A
A → ab
N={S,A}, T={a,b}
S → A ab A ab A
A → ε | a A | b A

Untersuchen Sie, welche Wörter die jeweilige Sprache bilden, und erläutern Sie, weshalb die Grammatiken kontextfrei sind.

Hilfe 1 (Ableiten):
Leiten Sie aus jeder Grammatik einige kurze Wörter ab und beschreiben Sie, was sie gemeinsam haben.
Hilfe 2 (Kontextfrei):
Prüfen Sie: Steht links in jeder Regel genau ein Nichtterminal?

Die drei Sprachen sind regulär. Entwickeln Sie geeignete reguläre Grammatiken.

Hilfe 1 (Vorgehen):
Beschreiben Sie zuerst die Sprache in Worten und bauen Sie die Wörter dann von links nach rechts auf.

Erläutern Sie detailliert, wie Sprachen und ihre Grammatiken zusammenhängen.

Hilfe 1 (Begriffe):
Eine Sprache ist eine Menge von Wörtern, eine Grammatik ein Regelwerk. Kann es zu einer Sprache mehrere Grammatiken geben?
Aufgabe 5: Palindrome und Kellerautomaten (Gruppenarbeit)

Im Abschnitt zu regulären Sprachen und DEA haben wir gesehen, dass beide Modelle zusammenhängen. Auch für kontextfreie Sprachen gibt es ein äquivalentes Automatenmodell:

Eine Sprache ist genau dann kontextfrei, wenn es eine kontextfreie Grammatik gibt, die diese Sprache erzeugt. Äquivalent hierzu ist: Eine Sprache ist genau dann kontextfrei, wenn es einen NKA gibt, der Akzeptor dieser Sprache ist.

Ein Palindrom ist ein Wort, das von vorne und hinten gelesen gleich ist, z. B. anna, reittier oder rentner. Erstellen Sie eine Grammatik zur Sprache der Palindrome aus Kleinbuchstaben.

Hilfe 1 (Von außen nach innen):
Ein Palindrom hat außen gleiche Buchstaben. Regeln wie S → a S a erzeugen sie. Wie endet ein Palindrom in der Mitte (gerade und ungerade Länge)?

Entwickeln Sie eine kontextfreie Grammatik für alle Palindrome mit ungerader Wortlänge über dem Alphabet {a, b, c}, wobei c nur in der Wortmitte vorkommt.

Hilfe 1 (Mitte):
Die Mitte ist hier immer genau ein c. Welche Regel beendet deshalb die Ableitung?

Entwerfen Sie einen Kellerautomaten, der Akzeptor dieser Palindrome ist.

Hilfe 1 (Erste Hälfte):
Legen Sie alle Zeichen vor dem c in den Keller.
Hilfe 2 (Zweite Hälfte):
Nach dem c muss jedes Zeichen mit dem obersten Kellerzeichen übereinstimmen. Am Ende darf nur noch # im Keller liegen.

Die Abbildung zeigt den Vorschlag eines Kellerautomaten, der Akzeptor aller Palindrome über {a, b} ohne Trennzeichen in der Mitte sein soll. Analysieren Sie seine Funktionsweise und vergleichen Sie ihn mit Ihrem Automaten aus c). Hinweis: Eine Umschreibung von „nicht-deterministisch“ ist „nicht eindeutig vorbestimmt“.

Hilfe 1 (Wo gibt es zwei Möglichkeiten?):
Suchen Sie in \(q_0\) Situationen, in denen zwei Übergänge passen. Was „rät“ der Automat dort?
Hilfe 2 (Testen):
Testen Sie aba, abba, a und das leere Wort. Welche werden akzeptiert?
Aufgabe 6: HTML als Sprache (Partnerarbeit)

HTML-Dokumente bestehen aus verschiedenen Tags, die Inhalte strukturieren. Ein Tag ist immer durch < und > eingegrenzt. Die Sprache aller korrekten HTML-Dokumente nennen wir \(L_{HTML}\). Ein Beispiel:

<html>
  <head><title>Beispiel für HTML</title></head>
  <body>
    <h1>Willkommen auf meiner Webseite!</h1>
    <div>
      <p>Besuche <a href="https://www.example.com"></a> für mehr Informationen.</p>
      <div>
        <p>Ein weiterer Absatz.</p>
        <div><p>Und noch ein Absatz in einer tieferen Ebene.</p></div>
      </div>
    </div>
  </body>
</html>

Begründen Sie, weshalb \(L_{HTML}\) nicht regulär ist.

Hilfe 1 (Schachtelung):
Zu jedem öffnenden Tag gehört ein schließendes, und Tags können beliebig tief geschachtelt werden. Was müsste sich ein DEA merken?

Entwickeln Sie eine kontextfreie Grammatik, die alle Wörter von \(L_{HTML}\) erzeugt. Sie können selbst entscheiden, ob Sie mehr Elemente als im Beispiel berücksichtigen.

Hilfe 1 (Aufbau):
Beginnen Sie außen: S → <html> HEAD BODY </html>. Dann zerlegen Sie HEAD und BODY weiter.
Hilfe 2 (Wiederholungen):
Für beliebig viele Elemente im Body hilft ein Nichtterminal ELEMS → ELEM ELEMS | ε.

Entwerfen Sie einen Kellerautomaten, der Akzeptor der Sprache \(L_{HTML}\) ist.

Hilfe 1 (Tags im Keller):
Legen Sie für jedes öffnende Tag ein Zeichen in den Keller. Ein schließendes Tag darf nur gelesen werden, wenn das passende Zeichen oben liegt.
Aufgabe 7: SQL-Abfragen prüfen (Gruppenarbeit)

Datenbank-Managementsysteme benötigen Parser, die eingegebene SQL-Abfragen auf Korrektheit prüfen. Die Menge aller gültigen Abfragen ist \(L_{SQL}\). Wir betrachten eine Datenbank zur Verwaltung eines Online-Adventurespiels:

Held
HeldIDNameKlasseIDLevel
1Eldrin110
2Thalia215
3Kaelthas320
4Sylvara112
5Borin214
Klasse
KlasseIDKlassennameBeschreibung
1KriegerStarker Nahkämpfer
2ZwergRobuster Kämpfer mit Hammer
3MagierMeister der magischen Künste
Item
ItemIDNameTypWert
1LangschwertWaffe150
2SchildRüstung100
3HeiltrankTrank50
4ZauberstabWaffe200
5ZwergenhelmRüstung120
Inventar
HeldIDItemIDMenge
111
135
221
241
341
332
411
521
551

Die folgenden vier SQL-Abfragen sind fehlerhaft. Analysieren Sie, was sie ausgeben sollen, erläutern Sie ihre Funktionsweise und korrigieren Sie die Fehler.

-- SQL-Abfrage 1
SELECT h.Name AS HeldName, k.Klassenname AS Klasse
FROM Helden h
WHERE h.KlasseID = k.KlasseID;

-- SQL-Abfrage 2
SELECT h.Name AS HeldName, i.Name AS ItemName, iv.Menge
FROM Inventar iv
JOIN Helden h ON iv.HeldID = h.HeldID
JOIN Items i ON ItemID = ItemID
WHERE h.Name = 'Kaelthas';

-- SQL-Abfrage 3
SELECT SUM AS GesamtanzahlItems
FROM Inventar iv;

-- SQL-Abfrage 4
SELECT k.Klassenname AS Klasse, i.Typ SUM(iv.Menge) AS GesamtanzahlItems
FROM Inventar iv, Helden h, Klassen k, Items i
WHERE iv.HeldID = h.HeldID AND h.KlasseID = k.KlasseID AND iv.ItemID = i.ItemID
GROUP BY k.Klassenname
ORDER BY k.Klassenname, i.Typ;
Hilfe 1 (Bestandteile):
Prüfen Sie jede Abfrage der Reihe nach: Werden alle Tabellenaliase (z. B. k) im FROM-Teil eingeführt? Stimmen die Schlüsselwörter und ihre Reihenfolge?

Untersuchen Sie, unter welchen Voraussetzungen \(L_{SQL}\) regulär ist, und begründen Sie, dass dies unter normalen Umständen nicht der Fall ist.

Hilfe 1 (Schachtelung):
Welche Teile von SQL können beliebig tief geschachtelt werden (Klammern, Unterabfragen)? Was passiert, wenn man die Tiefe begrenzt?

Entwickeln Sie eine kontextfreie Grammatik, die alle Wörter von \(L_{SQL}\) erzeugt und mindestens Auswahl (SELECT), Tabellen (FROM), Bedingungen (WHERE oder JOIN) und Gruppierung (GROUP BY) abdeckt. Die Grammatik soll nur syntaktisch korrekte Abfragen erzeugen; die semantische Korrektheit wird ignoriert (vgl. „Ich klettere auf einen Berg.“ und „Ich klettere auf einen Weltraum.“ – beide Sätze sind syntaktisch korrekt, aber nur einer ist semantisch richtig).

Hilfe 1 (Aufbau):
Beginnen Sie mit S → SELECT SELECT_LIST FROM TABLE_EXPR WHERE_OPT GROUP_OPT und zerlegen Sie dann jedes Nichtterminal.
Hilfe 2 (Optionale Teile):
Optionale Teile wie WHERE erhalten eine Regel mit ε, z. B. WHERE_OPT → WHERE CONDITION | ε.
Aufgabe 8: Formale und natürliche Sprachen (Partnerarbeit)

Vergleichen Sie die folgenden Beispiele:

  • (1) „Ich sah den Mann mit dem Fernglas.“
  • (2) „Der Berg klettert auf den Wanderer.“
  • (3) SELECT Name FROM Schueler WHERE Klasse = '12b'
  • (4) SELECT Name WHERE Klasse = '12b' FROM Schueler

Untersuchen Sie die Beispiele (1) bis (4) jeweils auf syntaktische Korrektheit und Eindeutigkeit der Bedeutung.

Hilfe 1 (Syntax und Semantik):
Syntax betrifft den Aufbau (Welche Wörter stehen in welcher Reihenfolge?), Semantik die Bedeutung. Prüfen Sie beides getrennt.
Hilfe 2 (Beispiel (1)):
Wer hat das Fernglas: die Person, die sieht, oder der Mann? Gibt es mehr als eine Lesart?
Hilfe 3 (Beispiel (4)):
Vergleichen Sie die Reihenfolge der Schlüsselwörter mit Beispiel (3). Was macht ein Datenbanksystem mit dieser Eingabe?

Vergleichen Sie formale und natürliche Sprachen hinsichtlich Alphabet bzw. Wortschatz, Grammatik, Eindeutigkeit und Umgang mit Fehlern.

Hilfe 1 (Gesichtspunkte):
Legen Sie eine Tabelle mit den Spalten „formale Sprache“ und „natürliche Sprache“ an und tragen Sie zu jedem Gesichtspunkt ein Beispiel ein.
Hilfe 2 (Umgang mit Fehlern):
Ein Mensch versteht auch einen Satz mit einem Grammatikfehler. Wie reagiert ein Compiler auf eine fehlende Klammer?

Beurteilen Sie die Aussage: „Ein Computer könnte Deutsch genauso sicher verarbeiten wie Java, man müsste nur genug Grammatikregeln aufschreiben.“

Hilfe 1 (Mehrdeutigkeit):
Würde eine vollständige Grammatik das Problem aus Beispiel (1) lösen? Welche Information fehlt dem Computer dort?
Hilfe 2 (Veränderung):
Natürliche Sprachen verändern sich ständig und werden nicht nach festen Regeln „erfunden“. Was bedeutet das für eine Grammatik des Deutschen?
🎉 Ausgezeichnet – Alle Aufgaben abgeschlossen!

Vergleichen Sie Ihre Ergebnisse nun mit der Musterlösung.