Diese Webseite speichert Cookies und verarbeitet personenbezogene Daten, um das Angebot jener zu verbessern. Sie können allgemein die entsprechenden Dienste uneingeschränkt zulassen („Einverstanden“) oder nur eingeschränkt zulassen („Einschränken“). Sie können diesen Hinweis aber auch ausblenden, dann werden die Dienste nur eingeschränkt zugelassen. Die Auswahl wird in einem Cookie für ein Jahr gespeichert, bei der Ausblendung nur bis zum Sitzungsende (mittels eines Session-Cookies).

Sie können auch weitere Einstellungen vornehmen (zum Auf-/Einklappen hier klicken):
AdSense
Analytics
  1. Mit der Einstellung „AdSense komplett erlauben“ erklären Sie sich damit einverstanden, dass die Webseite Cookies speichert, um für Sie personalisierte Werbung bereitstellen zu können. Mit der Einstellung „AdSense eingeschränkt erlauben“ werden keine solchen Cookies verwendet und es wird Werbung angezeigt, die sich am Thema der einzelnen Seite orientiert. In jedem Fall wird aber von Google ein Cookie gesetzt, durch das ein Betrug verhindert wird.
  2. Mit der Einstellung „Analytics komplett erlauben“ willigen Sie darin ein, dass die Webseite Cookies speichert, durch die es ermöglicht wird, Sie bei einem erneuten Besuch zuordnen zu können. Mit der Einstellung „Analytics eingeschränkt erlauben (Session-Cookie)“ wird ein Session-Cookie nur zur Aufzeichnung der aktuellen Sitzung angelegt. Mit der Einstellung „Analytics eingeschränkt erlauben (ohne Session-Cookie)“ wird kein Cookie gesetzt, sondern stattdessen ein Zählpixel mit einer nicht zuordenbaren ClientId.

Sie können auch auf der Datenschutzseite weitere Informationen einholen. In diesem Fall stimmen Sie einer eingeschränkten Nutzung zu (ohne Setzung eines Analytics-Cookies), um den Inhalt lesen zu können. Die Zustimmung wird mit einem Session-Cookie gespeichert. Sie können auf der Datenschutzseite die Einstellungen entsprechend anpassen.

Überspringe die Navigation
Schulstoff.org
Kontrastmodus umschalten
Zählmarke Endliche Automaten
Anmerkung: In dieser Jahrgangsstufe geht es vor allem um die Programmierung mit Java. Zum Erlernen eignet sich unter anderem das Programm BlueJ.
Inhaltsverzeichnis [Anzeigen] [Verbergen]

Endliche Automaten

Einführung

Programme können in Zustandsdiagrammen dargestellt werden. Darin werden Übergänge und Aktionen dargestellt. Wird eine Aktion zeitgleich mit dem Übergang gestartet, spricht man von ausgelösten Aktionen.

Die verschiedenen Aktionen führen wiederum zu verschiedenen Zuständen. Ist die Anzahl der Zustände begrenzt, also endlich, spricht man von einem endlichen Automat. Mithilfe eines solchen endlichen Automaten lassen sich viele (aber nicht alle) Systeme modellieren.

Ein endlicher Automat ist eine Art „Black Box“. Befindet sich diese Black Box nach Abarbeitung der Eingabefolge in einem ausgezeichneten Zustand, dem sogenannten Endzustand, so handelt es sich um eine akzeptierte Folge, ansonsten hat sie die Eingabe nicht akzeptiert.

Beispiel: Schwimmbadautomat

Der Eintritt in ein Schwimmbad kostet 2€. Nach Eingabe von Münzen im Gesamtwert von mindestens 2€ öffnet der Automat die Schranke, sonst nicht. Er akzeptiert lediglich Münzen im Wert von 0,50€, 1€ und 2€.

Das zugehörige Zustandsdiagramm sieht so aus, wobei q Zustand beschreibt:

Zustandsdiagramm für einen Endlichen AutomatenZustandsdiagramm für einen Endlichen Automaten
Zustandsdiagramm für einen Endlichen Automaten

Zustandsübergangstabelle

Das Zustandsdiagramm lässt sich auch tabellarisch darstellen. Diese Tabelle wird als Zustandsübergangstabelle bezeichnet. Hierbei steht in der Kopfzeile die Aktion, die den Übergang auslöst, in der linken Spalte der Aggregatszustand des Übergangs und in der Zelle die ausgelöste Aktion sowie den Zielüberstand des Übergangs[1]Informatik 3, S. 83..

Beim Schwimmbadautomaten sähe die Tabelle etwa wie folgt aus:

0,5 1,0 2,0
start q0,5 q1 q2
q0,5 q1 q1,5 q2
q1 q1,5 q2 q2
q1,5 q2 q2 q2
q2 q2 q2 q2

Häufig werden in der Informatik „Wörter“ als Zeichenketten (häufig nur Zeichen a und b) oder auch „Zahlen“ als Ziffernketten eingegeben und daraufhin untersucht, ob sie eine bestimmte Bedingung erfüllen.

Implementierung von endlichen Automaten

Endliche Automaten werden durch ein spezielles Objekt implementiert. Dabei wird der Zustand des Objekts durch eine konkrete Kombination der Attributswerte definiert. Häufig werden allerdings nicht alle Attributswerte benötigt. Aus diesem Grund kann ein spezieller Zustand verwendet werden, dessen Wert den Zustand des simulierten Automaten beschreibt[2]Informatik 3, S. 83..

« Vorherige Seite
Auf einer Seite lesen
Nächste Seite »