1.1 Einstieg endlicher Automat (EA)
Zum Einstieg spielen wir ein Spiel und lösen ein Quiz.
Spiel
Wir befinden uns in Trainsylvania, eine fiktive Stadt, in welcher es nur die zwei Züge A und B gibt. Leider existiert aktuell nur die folgende Karte mit den Stationen aber ohne Zugverbindungen.
Genauer sind wir bei der Station 1: Airport. Unser Ziel ist es, nach Station 5: Harbour zu kommen. Doch welche Zugverbindung bringt uns am schnellsten zum Ziel? Finden Sie auch eine längere Variante?
Fahren Sie, indem sie auf dieser verlinkten Seite auf den jeweiligen Knopf drücken, mit den Zügen A und B in Trainsylvania umher, bis Sie den schnellsten Weg von Airport zu Harbour finden. Kennen Sie alle Zugverbindungen von Trainsylvania? Zeichnen Sie eine vollständige Karte.
Tipp Lösung
Quiz
Hier ist eine Karte einer anderen Stadt. Anstatt Namen haben die Stationen nur noch Zahlen.
Starten wir bei der Station 1 (dies kennzeichnen wir mit dem Pfeil, der von aussen kommt) und suchen wir unseren Weg nach Station 4. (Das Ziel kennzeichnen wir, indem wir es doppelt umkreisen.)
- Was ist die kürzeste Verbindung von Station 1 zu Station 4?
- Wo landen wir, wenn wir bei Station 1 starten und die Züge ABBAA nehmen?
- Wo landen wir, wenn wir bei Station 1 starten, 20 Stationen fahren, wobei wir abwechslungsweise die Züge B, A, B, A, etc. nehmen?
- Suchen Sie eine einfache Beschreibung einer Folge von 100 Stationen, welche uns von der Station 1 zur Station 4 bringt.
Es geht hier nicht darum, den kürzesten Weg zu finden, sondern die Frage “Komme ich mit den dieser Zugverbindung (z. B. AABBA) an meiner Wunschdestination an oder nicht?”. Wenn wir beispielsweise bei der Station 3 stehen, ist es egal, wie wir dahin gekommen sind. Entscheidend ist nur, ob wir an unserem Ziel ankommen.
Informelle Definition eines endlichen Automaten
Die letzte Karte mit den Kreisen und Pfeilen beschreibt ein fundamentales Konzept der theoretischen Informatik, welches endlicher Automat heisst. Dabei sind die (einfach- und doppelt-)umkreisten Stationen Zustände (“Wo bin ich gerade?”), die doppeltumkreisten Stationen, die speziellen akzeptierenden Zustände (“Wo ist mein Ziel?”) und die Pfeile Zustandsübergänge (“Mit welchem Zug komme ich zur nächsten Station/zum nächsten Zustand?”). Der Pfeil, der von aussen kommt, gibt an, wo wir starten. Dieser Zustand ist der Startzustand. Das Wort “endlich” bezieht sich darauf, dass es nur endlich viele Zustände gibt.
Ein endlicher Automat beantwortet Ja-Nein Fragen, also Fragen, die mit ja oder nein beantwortet werden können.
Mehr dazu lernen wir im nächsten Abschnitt.
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 1_1_EA_Notizen.