Es ist passiert. Du warst auf einer längeren Geburtstagsparty, kommst früh morgens nach Hause und stellst erschrocken fest, dass du deinen Schlüssel wohl zuhause vergessen hast! Durch Klingeln scheint bei dir zuhause niemand mehr wach zu werden. Da fällt dir ein, dass deine Eltern kürzlich an eurem Garagentor ein smartes Schloss mit Keypad angebracht haben. Jede Person in eurer Familie hat eine eigene PIN, mit welcher man das Tor öffnen und schließen kann.
Ob dir deine PIN noch einfällt, ist fraglich. Nach einigen erfolglosen Versuchen fragst du dich langsam, wie das System hinter dem Keypad eigentlich arbeitet.
- (PA-MP) Ein PIN besteht aus vier Ziffern, welche nacheinander eingegeben werden. Zu jedem Zeitpunkt prüft das Keypad, ob die Eingabe teilweise korrekt ist. Ist die PIN abschließend korrekt eingegeben, wird das Tor geöffnet. Angenommen, deine PIN hat als erste Ziffer eine 4. Überlegt euch, welchen Unterschied die Eingabe der Ziffer 4, im Vergleich zur Eingabe einer anderen Ziffer, für den Computer, welcher die Eingabe der ersten Ziffer auf dem Keypad verarbeitet, darstellt.
Code incorrectCadenas ouvert !
- (EA) Angenommen deine PIN ist 4321.
Vervollständige den oben abgebildeten Zustandsgraph, indem du alle weiteren Eingabemöglichkeiten umsetzt und entsprechende Zustände und Zustandsübergänge ergänzt. - Suchen Sie sich einen Partner oder eine Partnerin.
- Tauschen Sie sich über ihren Zustandsgraphen aus und einigen Sie sich auf eine gemeinsamen Lösung.
- Ergänzen Sie die folgende Zustandsübergangstabelle anhand ihres Zustandsgraphens.
Auf fachlicher Ebene bezeichnet man das gesamte Szenario mit dem Keypad als deterministisch endlichen Autaomten, kurz DEA.
Ein DEA ist ein sogenannten 5-Tupel (also besteht er aus fünf Komponenten). Das 5-Tupel eines DEA besteht aus (Q, s, Σ, F, δ), wobei die einzelnen Komponenten wie folgt definiert sind:
| Komponente | Definition |
|---|---|
| Q | Q ist eine nicht leere, endliche Menge von Zuständen, in denen sich der DEA befinden kann. Bsp. beim Keypad: Q={q0, q1, q2, q3, q4, qF} |
| s | s∈Q ist der Startzustand, in dem sich der DEA zu Beginn befindet. Bsp. Keypad: s=q0 . Achtung: Es ist immer nur ein Startzustand möglich. |
| Σ | Σ ist ein nicht leeres, endliches Eingabealphabet, also alles, was der Automat als
Eingabezeichen erhalten kann. Bsp. Keypad: Σ={0 , ...,9} |
| F | F ist die Menge der akzeptierten Endzustände, also eine Teilmenge von Q. Bsp. Keypad: F={q4} . Achtung, es darf auch mehrere Endzustände geben. |
| δ | δ ist die Übergangsfunktion, die jeder Kombination aus aktuellen Zustand und einem Eingabezeichen einen Folgezustand zuordnet. Diese Funktion stellt man mathematisch durch δ: Q×Σ→Q dar. Das bedeutet, dass einem Paar, z. B. (q0, 4) bei unserem Keypad ein Folgezustand, hier q1 , zugeordnet wird: (q0, 4)→q1. Die Übergangsfunktion kann in Form einer Tabelle angegeben werden. |
- Im Osnabrücker Zoo hat die Direktorin ein modernes
Schloss am Rüsselspringergehege angebracht. Dieser Schritt
wurde notwendig, da auch nicht berechtigte Mitarbeitende
ständig die Rüsselspringer streicheln wollten.
Das Schloss wird über ein Keypad bedient.
- 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 Zustandsgraph, welcher als Akzeptor der erlaubten Eingaben arbeitet. Hinweis: Mit der Webanewendung FLACI können Sie endliche Automaten erstellen und testen. Sie ist unter der Aufgabe eingebettet oder sie klicken auf den Schriftzug, dann erreichen Sie die Webseite auch.
- Geben Sie für Ihren DEA auch die formale Darstellung als 5-Tupel an.
- 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 und in einem dafür vorgesehenen Programm
speichern. Aus Sicherheitsgründen, wird die Zusammensetzung einer erlaubten PIN verschärft.
Standard Anspruchsvoll Schwierig 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. - Geben Sie je zwei strukturell verschiedene akzeptierte und nicht akzeptierte Eingaben an.
- Entwerfen Sie einen DEA in Form eines Zustandsgraph, welcher als Akzeptor der erlaubten Eingaben arbeitet.
Standard Anspruchsvoll Schwierig Eine PIN muss nun aus mindestens drei und höchstens vier Ziffern bestehen. Außerdem darf eine PIN nicht vier gleiche Ziffern beinhalten. Eine PIN muss nun aus mindestens drei und höchstens fünf Ziffern bestehen. Außerdem darf eine PIN nicht drei gleiche Ziffern beinhalten. Eine PIN muss nun aus mindestens vier und höchstens sechs Ziffern bestehen. Außerdem darf eine PIN nicht vier aufeinanderfolgenden Ziffern in aufoder absteigender Reihenfolge beinhalten. - Geben Sie je zwei strukturell verschiedene akzeptierte und nicht akzeptierte Eingaben an.
- Entwerfen Sie einen DEA in Form eines Zustandsgraph, welcher als Akzeptor der erlaubten Eingaben arbeitet.
- 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.
- Die Keypads werden verbessert. An einem Keypad können nun Ziffern, Klein- und Großbuchstaben
und Sonderzeichen eingegeben werden.
Standard Anspruchsvoll Schwierig Ein erlaubtes Passwort muss mindestens aus vier Zeichen und mindestens zwei der vier Zeichenarten beinhalten. Ein erlaubtes Passwort muss mindestens aus vier Zeichen und mindestens drei der vier Zeichenarten beinhalten. 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. - Geben Sie je zwei strukturell verschiedene akzeptierte und nicht akzeptierte Eingaben an.
- Entwerfen Sie einen DEA in Form eines Zustandsgraph, welcher als Akzeptor der erlaubten Eingaben arbeitet.
- Erstellen Sie ebenfalls den Zustandsgraphen zu Ihrem DEA.
- Geben Sie die vom DEA akzeptierte Sprache an.
- Geben Sie je zwei Wörter an, welche vom DEA akzeptiert bzw. nicht akzeptiert werden.
- Erstellen Sie eine konkrete Angabe der Wörter der Sprache, welche vom DEA akzeptiert wird.
- Geben Sie die formale Definition des DEA an.
Setzen Sie sich zunächst inhaltlich etwas mit dem Thema auseinander, indem Sie einige der Aufgaben bearbeiten (30Min). Bearbeiten Sie aber bitte Aufgabe 1a und b.
Finden Sie sich in einer schulartheterogenen Gruppe (3-4 Leute) zusammen und bearbeiten Sie die folgenden Aufgaben (45Min):
- Vergleichen Sie das Herangehen bei der Bearbeitung der Aufgaben 1a und 1b.
- Sammeln Sie zunächst Beispiele für den Einsatz von endlichen Automaten aus Ihrem Alltag.
- Wählen Sie in der Gruppe einen Kontext aus und entwickeln Sie dazu eine Aufgabenfolge, die zunehmenden anspruchsvoller wird.
- Präsentieren Sie einer anderen Gruppe Ihre Aufgabe und lassen Sie sich Rückmeldungen geben.
Spam-Filter sind heutzutage ein wichtiger Bestandteil eines Emailprogramms. Auf Seiten der Provider findet bereits eine Filterung statt. Eine Verteilung von Themen, die bei Spam 2019 auftreten und von Statista veröffentlicht und von onlinesicherheit.at aufbereitet wurde, ist unten abgebildet.
Das Wort "bitcoin" soll im folgenden Beispiel von einem Automaten erkannt und alle E-Mails mit "bitcoin" im Betreff sollen herausgefiltert werden. Der Zustandsgraph des entsprechenden DEA ist unten abgebildet.
Trotz der recht einfachen Aufgabe ist der DEA ziemlich komplex und wenig übersichtlich. Versuchen wir es anders...
Es fällt auf, dass beim Startzustand die Eingabe "b" mehr als einmal vorkommt. Es handelt sich bei diesem Automaten nicht mehr um einen deterministischen Automaten, da es Zustände gibt, von denen aus der Zustandsübergang nicht mehr eindeutig vorbestimmt, also determiniert, ist. Dieser Automat testet zu jedem Zeitpunkt eines Eingabezeichens alle Möglichkeiten, die es mit dieser Eingabe gibt und wählt schließlich eine aus, die in einen Endzustand führt, sollte dies möglich sein. Solch einen Automaten nennt man nichtdeterministischen endlichen Automaten - NEA.
Ein NEA ist ein sogenannten 5-Tupel (also besteht er aus fünf Komponenten). Das 5-Tupel eines DEA besteht aus (Q, s, Σ, F, δ), wobei die einzelnen Komponenten wie folgt definiert sind:
| Komponente | Definition |
|---|---|
| Q | Q ist eine nicht leere, endliche Menge von Zuständen, |
| s | s∈Q ist der Startzustand, in dem sich der NEA zu Beginn befindet. |
| Σ | Σ ist ein nicht leeres, endliches Eingabealphabet, also alles, was der Automat als Eingabezeichen erhalten kann. |
| F | F ist die Menge der akzeptierten Endzustände, also eine Teilmenge von Q. |
| δ | δ ist die Übergangsrelation, die jeder Kombination aus aktuellen Zustand und einem Eingabezeichen mindestens einen Folgezustand zuordnet. Diese Funktion stellt man mathematisch durch δ: Q×Σ→Q dar. |
Bei den Zustandsübergängen kann es bei den NEA auch sogenannte ε -Übergang geben. Der NEA hat damit auch ohne Eingabezeichen die Möglichkeit einen ε -Übergang in einen Folgezustand zu wählen.
- Analog zum Spamfilter NEA aus dem Einstieg soll nun ein weitere Spamfilter erstellt werden.
- Entwerfen Sie sowohl einen DEA als auch einen NEA, welcher den Spamfilter für das Wort "kredit" darstellt.
- Erklären Sie anhand Ihres Ergebnisses den Unterschied zwischen DEA und NEA.
- Erweitern Sie Ihren DEA/NEA aus Aufgabe 1a so, dass er zusätzlich das Wort "geld" prüft.
- Im englischen Sprachraum gibt es, wie auch in der deutschen Sprache, das Bestreben, eine geschlechtergerechte Sprache zu benutzen. Ein typisches Verfahren ist, das Teilwort man durch
das Wort person zu ersetzen, so dass zum Beispiel aus dem Wort salesman das Wort salesperson wird.
Im Folgenden sollen englischsprachige Texte auf den Gebrauch von geschlechtergerechter
Sprache rein syntaktisch untersucht werden. In einem ersten Ansatz sollen dazu die Wörter
herausgefiltert werden, die als Teilwort die Zeichenfolge man haben.
Der folgende endliche Automat A, der durch einen Übergangsgraphen in Abbildung 1 angegeben ist, wird entworfen, um einzelne Wörter darauf zu untersuchen. Dabei wird davon ausge-
gangen, dass nur kleine Buchstaben in einem Wort vorkommen.
Abbildung 1: NEA Teilwortproblem.
Das Zeichen x steht für einen beliebigen Kleinbuchstaben des Alphabets mit Ausnahme von a, m, n.
- Überführen Sie den Zustandsgraphen in eine Zustandsübergangstabelle.
- Begründen Sie, dass es nicht um einen deterministisch endlichen Automaten handelt.
- Begründen Sie, wie man feststellen kann, ob ein Wort von diesem Automaten akzeptiert wird.
- Zeigen Sie, dass die Wörter salesman und command zur Sprache des Automaten gehören.
- Der Automat, der durch den Übergangsgraphen in Abbildung 1 gegeben ist, soll erweitert
und in einen deterministischen Automaten umgewandelt werden, der zusätzlich das Teilwort
men akzeptiert.
Entwickeln Sie den Zustandsübergangsgraphen eines deterministischen endlichen Automaten, der diesen Anforderungen entspricht. - Teilwortprobleme, wie das man oder men lassen sich mit n+1 Zustände in einem DEA lösen (n: Anzahl Buchstaben des Teilworts). Nun wird behauptet, dass ein spezielles Teilwortproblem nur dann von einem DEA mit n+1 Zuständen gelöst werden kann, wenn das Teilwort keine doppelten Zeichen enthält. Also würde mommy oder book (als Teilwörter) nicht mit einem DEA aus n+1 Zuständen gelöst werden können.
Begründen Sie, ob diese Aussage korrekt ist.
Bei dem Autoamten handelt es sich nicht um einen DEA, da der Zustandsübergang von q0 zu q1 nicht eindeutig ist. Mit der Eingabe m kann sowohl in q1 als auch in q0 übergegangen werden und somit ist der Automat nicht deterministisch.
Das Eingabewort muss mittels Zustandsübergängen im Endzustand landen.
q0 -s->q0-a->q0-l->q0-e->q0-s->q0-m->q1-a->q2-n->q3; wird akzeptiert, da im Endzustand.
q0-c->q0-o->q0-m->q0-m->q1-a->q2-n->q3-d->q3; wird akzeptiert, da im Endzustand.
Es wird ein Beweis per Widerspruch geführt, also wird geschaut, ob es einen DEA mit n+1 Zuständen gibt, trotz dessen dass ein solcher spezieller Fall vorliegt.
Finden Sie sich in einer schulformhomogenen Gruppen 2-3 Leute zusammen:
- Bearbeiten Sie gemeinsam die Aufgabe 2.
- Angenommen Sie müssten das Thema endliche Automaten im Unterricht thematisieren. Würden Sie zuerst NEA oder DEA vermitteln?
Im Osnabrücker Zoo hat die Direktorin ein modernes Schloss angebracht, welches über ein Pad bedient werden kann. Mögliche Eingaben sind die Ziffern 0 und 1. Das Schloss öffnet sich, wenn eine gleiche Anzahl von Nullen und Einsen eingegeben werden.
- Um den notwendigen DEA zu entwerfen, ist die Länge der Eingaben zunächst auf 2 begrenzt. Geben Sie alle akzeptierten und zwei strukturell verschiedene nicht akzeptierte Eingaben an.
- Entwerfen Sie einen DEA zu a) in Form eines Zustandsgraph, welcher als Akzeptor der erlaubten Eingaben arbeitet.
- Untersuchen Sie, wie sich der Zustandsgraph aus b) verändern muss, wenn die Eingabelänge auf 4 erhöht wird.
- Untersuchen Sie, wie sich der Zustandsgraph verändern muss, wenn beliebig aber endlich lange Eingabewörter möglich sind.
Finden Sie sich in einer 3er bis 4er Gruppe zusammen (10Min):
- Finden Sie zunächsten weitere Beispiele, wo ein DEA nicht mehr als Akzeptor genügt.
- Laden Sie Ihre Ergebnisse im Miro-Board hoch.