Im Anschluss an die erfolgreiche Suche nach der Schatzinsel, kehren die Piraten gut gelaunt und stolz in die berüchtigte Bar „Zum plappernden Papagei“ zurück. Dort verwickeln sie andere Seefahrer in eine lebhafte Diskussion über die kniffligen navigatorischen Herausforderungen, die sie auf ihrer Suche gemeistert haben.

Überprüfe die Aussagen der Piraten:

1) Die Piraten 1 und 2 sind fast die gleiche Route gefahren. Worin liegt der Unterschied?

10) Pirat 3 erzählt: „Es war schrecklich! Schier endlos irrte ich zwischen den Inseln umher. Irgendwann habe ich wieder eine richtige Route gefunden … aber wo ich rausgekommen bin, keine Ahnung!“ Von welcher Insel aus hat er seine zahlreichen B-Routen beendet und zu welcher reiste er mit der folgenden A-Route?

11) Pirat 4 war recht lange unterwegs. Die anderen Piraten sagen: „Man kann ewig mit einer AABB-Folge herumirren!“ Sie sind sich dabei aber nicht ganz sicher und stürzen sich voller Elan auf die Karte, um es herauszufinden. Sie wissen aber, dass er die Schatzinsel erreicht hat.

100) Pirat 5 behauptet, seine Route hätte ihm eine ruhige Reise zur Schatzinsel beschert. Er könne sie jedem empfehlen. Aber stimmt das?

101) Pirat 6 behauptet, er sei mit seiner Routentaktik prima gefahren und wäre auch mit den wenigstens Aktionen an der Schatzinsel angekommen. Ist das so oder gibt es eine noch kürzere?

Level 1: Café-Roboter

In einem sehr modernen Café können Kunden von einem Roboter bedient werden. Der folgende Automat stellt ein typisches Szenario dar. Beschreibe mit eigenen Worten, was der Roboter tut.

Level 2: Türsteher

Beschreibe den Kontext, den dieser Automat eines Türstehers abbildet.

(Hier sieht man einen Automaten mit mehreren Endzuständen, der aber genauso funktioniert.)

Level 3: Ampel für Faultiere

Wenn ein Faultier an die rote Ampel kommt, bleibt sie für 5 Minuten im Zustand langsames Grün. Ansonsten nur für eine Minute in Grün. Nach der Grün-Phase wechselt sie für 30 Sekunden in Gelb und dann wieder in Rot, bis jemand kommt.

Zustände: Grün, langsames Grün, Gelb, Rot

Zeichne einen passenden Zustandsgraphen. Rot kann dabei gleichzeitig Start- und Endzustand sein.

Level 4: TikTok-Tanz-Automat

Eingabealphabet: Σ = {L, D}
für Like, Dance

Beschreibe, welche Wörter der TikTok-Tanz-Automat akzeptiert.

Level 5: Buchstaben-Folge-Automat

Zeichne den Zustandsgraphen eines Automaten, der beliebige Folgen der Buchstaben a und b erhält (z.B. babbababba) und der nur Wörter akzeptiert, die "ab" enthalten.

Zusatz: Erweitere den Automaten danach, so dass das Wort zusätzlich mit "ba" enden muss.

Bonuslevel: Eigener Automat

Überlege dir selbst einen Automaten. Er sollte nicht zu einfach und nicht zu komplex sein. Zeichne dann einen Zustandsgraphen dazu und teste, ob deine Sitznachbarn ihn verstehen.

Level 1: Lach-Automat

Beim folgenden Lach-Automaten soll geprüft werden, ob er ein DEA oder ein NEA ist. Er akzeptiert nur Wörter, welche korrekte Lachwörter sind:

hi!, hihi!, hihihi!, hihihihi!, ...

a) Überprüfe zuerst, ob der Automat richtig funktioniert!

b) Prüfe den Lach-Automaten auf alle 5 Merkmale eines EAs.

c) Entscheide begründet, ob es sich um einen DEA oder einen NEA handelt.

Level 2: Schnarch-Automat

Folgender Schnarch-Automat wird betrachtet:

a) Welche Wörter akzeptiert der Automat? (Was ist also seine Sprache?)

b) Entscheide begründet, ob es sich um einen DEA oder einen NEA handelt? (Ohne die Merkmale eines EAs zu prüfen.)

c) Jeder NEA kann in einen DEA umgewandelt werden, indem man ihn um Zustände und Übergänge ergänzt. Wandle den Schnarch-Automaten in einen DEA um.

Level 3: Schnarch-Automat

Gesucht ist der Zustandsgraph eines endlichen Automaten, der nur Eingaben akzeptiert, die mit „1“ beginnen und mit der Ziffernfolge „100“ enden.

Zeichne dazu einen Zustandsgraphen zunächst für einen NEA und dann für einen DEA.

Fülle die Lücken passend aus:

Ein Automat besteht aus ①______________ und den ②______________ zwischen ihnen. Unter den Zuständen gibt es besondere: Der ③______________ wird durch einen eingehenden Pfeil markiert, während ④______________ mit einem doppelten Kreis gekennzeichnet sind. Ein festgelegtes Schema bestimmt, in welchen ⑤______________ der Automat jeweils wechselt.

Führt eine ⑥______________ den Automaten in einen Endzustand, so nennt man sie ein Wort. Die Gesamtheit aller Wörter bildet die ⑦______________ . Dabei unterscheidet man ⑧______________ endliche Automaten (DEA), bei denen für jedes Eingabezeichen genau ein Übergang möglich ist, und ⑨______________ endliche Automaten (NEA), bei denen mehrere Übergänge zulässig sind.

Auf der Startseite sind alle gespeicherten Automaten aufgeführt. Über das Plus unten rechts kann ein neuer Automat erstellt werden.

Erstelle nun einen neuen Automaten.

Für einen neuen Automaten muss immer ein passender Name eingegeben und SPEICHERN geklickt werden.

Erstelle den Automaten "Pizza-bestell-Automat".

Das Video zeigt dir:

- Eigenes Eingabealphabet Σ festlegen.
- Partielle Funktion erlauben (immer aktivieren).
- Linkes Menü ausblenden.

Führe das nun selbst durch. Nutze ebenfalls M,S,A als Alphabet.

Jetzt geht es um das Zeichnen des Zustandsgraphen. Hier siehst du:

- Neuen Zustand erstellen.
- Weitere Zustände erzeugen.
- Übergänge definieren.
- Endzustand festlegen.

Führe das nun selbst durch. Nutze ebenfalls M,S,A als Alphabet.

Nachdem der Automat erstellt ist, kann er simuliert werden. Dazu gibt man ein Eingabewort ein und beobachtet, wie der es der Automat verarbeitet. Alle Eingabe wörter werden danach aufgeführt und ob sie vom Automaten akzeptiert werden oder nicht. Hier siehst du also:

- Simulation starten.
- Eingabewort festgelegen.
- Eingabewort bearbeiten.
- Verarbeitung beobachten.
- Akzeptierte Wörter sehen.

Simuliere nun selbst ein paar Eingabewörter mit dem Pizza-bestell-Automat und beobachte, wie er sie verarbeitet.

Die akzeptierten und abgelehnten Wörter erkennt man dann an dem grünen Haken oder roten Kreuz:

Du kannst die Einrichtungs-Anleitung von FLACI gleich wieder durch Anklicken minimieren und die Aufgaben lösen. Um einen neuen Automaten zu erstellen oder gespeicherte zu laden, klicke oben links auf "Meine Automaten".

Level 1: DEAs analysieren und verändern

a) Ohne FLACI: Gib jeweils ein Wort der Sprache an, das vom jeweiligen Automaten akzeptiert wird und begründe durch Angabe der durchlaufenen Zustände, dass das Wort akzeptiert wird.

b) Erstelle die Automaten in FLACI und überprüfe deine Lösungen im Simulationsmodus.

c) Beschreibe die akzeptierte Sprache allgemein.

d) Ein Fehlerzustand ist ein Zustand, von dem aus man nicht mehr in einen akzeptierenden Endzustand gelangen kann. Besitzen die Automaten einen Fehlerzustand?

e) Erweitere/Verändere Automat I) jeweils so, dass ...
(1) auch Wörter akzeptiert werden, die mit einem A enden.
(2) auch Wörter akzeptiert werden, die mit einem B beginnen.

Level 2: DEAs entwerfen 1

Die Sprache L_ung über dem Alphabet {0,1} besteht aus Wörtern, die nur aus den Ziffern 0 und 1 bestehen. Die Anzahl der 1en in jedem Wort muss aber stets ungerade sein. Wörter dieser Sprache sind z.B. 001, 10, 111, 10101, 1. Die Wörter 0, 1010, 11, 00011 oder 101 gehören nicht dazu.

a) Öffne über diesen Link den vorbereiteten Automaten. Stelle dort die Übergänge so ein, dass er der Aufgabe entspricht. Weitere Zustände sind nicht nötig!

b) Überprüfe die Funktionsweise deines Automaten anschließend mithilfe der oben aufgeführten Wörter.

c) Beschreibe, warum der Automat nur dann im Endzustand endet, wenn die Anzahl 1en ungerade ist.

d) Beobachte das Vorgehen der Simulation in der Tabelle unten links. Beschreibe, was dort schrittweise mit dem Eingabewort passiert. Nutze dafür ein etwas längeres.

Level 3: DEAs entwerfen 2

In Level 2 ging es um die Sprache L_ung = { Eingabe beinhaltet eine ungerade Anzahl an 1en }.

Erstelle in FLACI jeweils einen Automaten über dem Alphabet {0,1}, der folgende Sprachen akzeptiert:

a) L₀₁₀ = { Eingabe beinhaltet das Teilwort 010 }

b) L_{max 3} = { Eingabe beinhaltet höchstens drei 1en }

c) L_gerade = { Eingabe beinhaltet eine gerade Anzahl an 1en }

Falls du Hilfe benötigst:
a) Link: Automat mit fehlenden Übergängen.
b) Link: Automat mit fehlenden Übergängen.
c) Verändere deinen Automaten aus Level 2.

Level 4: Hawaiianisch

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 hawaiianischen Wörter sind nach folgenden Regeln aufgebaut: Einem Vokal können beliebig viele Vokale folgen, nach einem Konsonanten muss aber ein Vokal folgen und darf kein weiterer Konsonant stehen. Ein Wort darf also auch nur auf einen Vokal enden. Die Mindestlänge eines Hawaiianischen Wortes ist zwei.

Beispiel: „kumu“ heißt Lehrer und „hula“ ist ein Sammelbegriff für hawaiianische Tänze.

a) Entwerfe in FLACI einen endlichen Automaten, der hawaiianische Wörter erkennt.

b) Teste mithilfe deines Automaten, ob es sich bei folgenden Wörtern um hawaiianische Wörter handelt: ua, muumuu, lalla, lum, ipo (Du kannst sie hier kopieren und in FLACI einfügen.)

c) Handelt es sich auch bei folgenden Wörtern um hawaiianische Wörter?
aloha, ukulele, hamumumu, wikiwiki, halakahiki, humuhumunukunukuapuaa, napuamahalanaonekawehionakuahiweanenawawakehookakehoaalekeeaonanainaiakeao

Level 5: Auto-Kennzeichen

Autokennzeichen in Deutschland haben folgenden Aufbau:

- Ein Unterscheidungszeichen aus ein bis drei Buchstaben gibt den Verwaltungsbezirk an, in dem das Fahrzeug angemeldet ist. Beispielsweise M für die Stadt München, OL für Oldenburg oder BRA für Brake/Wesermarsch.

- Dann folgt ein Leerzeichen.

- Eine Erkennungsnummer aus ein bis zwei Buchstaben und ein bis vier Zahlen (führende Nullen sind nicht erlaubt) ermöglichen eine Identifikation des Fahrzeugbesitzers innerhalb des Verwaltungsbezirks (Trennung der Buchstaben und Zahlen durch ein Leerzeichen).

(- Zusammen sind es maximal acht Zeichen, was wir hier aber ignorieren.)

Entwerfe in FLACI den Zustandsgraphen eines DEA, der deutsche Autokennzeichen akzeptiert. Als Eingabealphabet kann {Leer, A…Z, 0…9, 1…9} verwendet werden, da nur unterschieden werden muss, ob ein Leerzeichen, ein Buchstabe, eine Ziffer von 0 bis 9 oder eine Ziffer von 1 bis 9 eigegeben wird.

Bonuslevel: Eingabeformular

Um bei einem Online-Versand bestellen zu können, muss ein Kunde z.B. Vor- und Nachnamen, Straße, Hausnummer, Postleitzahl, Mailadresse, etc. angeben. Diese werden oft bereits bei der Eingabe auf Fehler überprüft. So könnte z.B. eine Meldung ausgegeben werden, dass eine deutsche Postleitzahl fünfstellig sein muss oder eine Mailadresse ein @-Zeichen enthalten muss usw.

Modelliere für ein fiktives Eingabeformular je einen Automaten für jedes Eingabefeld. Treffe dabei bewusste Modellierungsentscheidungen, d.h. entscheiden Sie welche Eingabe der Automat ggf. akzeptieren soll, obwohl sie fehlerhaft ist, weil durch ein Abfangen der Eingabe beispielsweise der Automat sehr viel komplexer werden würde. Beispiel: Es gibt keine deutsche Postleitzahl, die mit 11 beginnt (siehe Grafik). Sie müssen also entscheiden, ob die Eingabe 11111 von Ihrem Automaten akzeptiert werden soll oder nicht.