Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
faecher:informatik:oberstufe:automaten:lepro:darstellung:start [21.09.2020 20:30] – [Eingabealphabet] sbel | faecher:informatik:oberstufe:automaten:lepro:darstellung:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Darstellung von Automaten ====== | ||
- | |||
- | |||
- | ==== Übersicht ==== | ||
- | |||
- | Um Abläufe einheitlich und verständlich mit Hilfe von Automaten darstellen zu können, | ||
- | ist es nötig, eine einheitliche Notation (Zeichen, Symbole, Schreibung) für Automaten zu | ||
- | verwenden. Diese lernst du im folgenden Kapitel kennen. Dabei werden die Begriffe Zu- | ||
- | stand, Übergang und Eingabe von Automaten erläutert. Ausserdem wird das Verhalten | ||
- | von Automaten auf Aktionen genauer betrachtet. | ||
- | |||
- | ==== Teillernziele ==== | ||
- | |||
- | Nach der Bearbeitung dieses Kapitels kannst du... | ||
- | |||
- | * unterscheiden, | ||
- | * Zustände und Übergänge in exemplarischen, | ||
- | * bestimmen, in welchem Zustand sich ein Automat nach einer bestimmten Eingabe befindet. | ||
- | * das Eingabealphabet eines Automaten bestimmen. | ||
- | |||
- | ====== Zustände und Übergänge ====== | ||
- | |||
- | Automaten kann man sich als eine Art " | ||
- | so wie zum Beispiel eine Kaffeemaschine. Eine Kaffeemaschine kann sich in verschiedenen Zuständen | ||
- | befinden (warten, Kaffee kochen, Kaffee warmhalten). Das festgelegte Schema sagt ihr, dass sie, wenn | ||
- | sie angeschaltet wird, Kaffee kochen soll. Wenn sie damit fertig ist, soll sie den Kaffee warmhalten, | ||
- | solange bis sie ausgeschaltet wird. | ||
- | |||
- | Im Allgemeinen haben alle Automaten ein solch vorgegebenes Schema. Automaten setzen sich zusammen aus Zuständen und Übergängen. Ein festgelegtes Schema gibt vor, wann ein Automat von einem | ||
- | Zustand in einen anderen übergeht. | ||
- | |||
- | <WRAP center round important 80%> | ||
- | **Definition** | ||
- | |||
- | Zu jedem Zeitpunkt befindet sich ein Automat in genau einem **Zustand**. **Übergänge** | ||
- | werden anhand einer Übergangsfunktion beschrieben. Eine Übergangsfunktion gibt | ||
- | an, mit welchem Zeichen von einem bestimmten Zustand in einen anderen gewechselt | ||
- | werden kann. | ||
- | </ | ||
- | |||
- | ===== Beispiel: Parkscheinautomat ===== | ||
- | |||
- | |||
- | Noch einmal zurück zu dem Parkscheinautomaten, | ||
- | |||
- | {{ : | ||
- | |||
- | Beschriftet man die Zustände und Übergänge ein wenig anders, sieht das Ganze so aus: | ||
- | |||
- | {{ : | ||
- | |||
- | |||
- | Dieser Automat hat die folgenden **Zustände**: | ||
- | |||
- | * **q1**. Der Automat wartet auf eine Eingabe. -> Wartezustand. | ||
- | * **q2**. Der Automat merkt sich, wie viel Geld eingeschmissen wurde. | ||
- | * **q3**. Der Automat druckt das Parkticket und gibt es aus. | ||
- | |||
- | Ausserdem hat der Automat die folgenden **Übergänge**: | ||
- | |||
- | * **v1**. Geld wird eingeschmissen. -> Der Automat wechselt von q1 zu q2. | ||
- | * **v2**. Es wird mehr Geld eingeworfen. -> Der Automat bleibt in q2 und zählt die Minuten. | ||
- | * **v3**. Der Knopf „Parkschein ausgeben“ wird gedrückt. -> Der Automat wechselt in q3. | ||
- | * **v4**. Das Parkticket wird entnommen. -> Der Automat wechselt zurück in q1. | ||
- | |||
- | Diese **Abstraktion** (Verallgemeinerung) hat den Vorteil, dass nun eine gewisse **Vergleichbarkeit** mit | ||
- | anderen Automaten geschaffen wird und so generelle Aussagen und allgemeine Betrachtungen möglich sind. | ||
- | |||
- | |||
- | === Aufgabe === | ||
- | |||
- | Eine einfache Supermarktkasse funktioniert folgendermaßen: | ||
- | |||
- | * Wird ein Preis eingegeben, addiert die Kasse diesen zum Gesamtpreis. | ||
- | * Drückt jemand die Taste „Kassieren“, | ||
- | * Wird die Geldlade geschlossen, | ||
- | |||
- | {{ : | ||
- | |||
- | Ordne die verschiedenen Zustände der Kasse und die Aktionen des Kassierers/ | ||
- | siererin den Zuständen und Übergängen der Skizze zu. | ||
- | |||
- | Vergleiche die Kasse mit dem Parkautomaten. | ||
- | |||
- | ====== Besondere Zustände ====== | ||
- | |||
- | Dir ist vielleicht schon aufgefallen, | ||
- | |||
- | |||
- | === Aufgabe === | ||
- | |||
- | Benenne die Start- und Endzustände der folgenden zwei Automaten: | ||
- | |||
- | {{ : | ||
- | |||
- | === Aufgabe === | ||
- | |||
- | Die Supermarktkasse von oben hat die folgenden Zustände und Übergänge. | ||
- | |||
- | {{ : | ||
- | |||
- | Die Kasse hat die folgenden Zustände: | ||
- | * q1. Wartezustand; | ||
- | * q2. Ein Preis wurde eingegeben, der Knopf „Kassieren“ wurde allerdings noch nicht gedrückt. | ||
- | * q3. Der Gesamtpreis wird angezeigt, und die Geldlade ist geöffnet. | ||
- | |||
- | Die Skizze hat die folgenden Übergänge: | ||
- | * v1. Der erste Preis eines Artikels wird eingegeben. | ||
- | * v2. Ein weiterer Preis wird eingegeben. | ||
- | * v3. Der Knopf „Kassieren“ wird gedrückt. | ||
- | * v4. Die Geldlade wird geschlossen. | ||
- | |||
- | Welchen Zustand könnte man hier als Endzustand wählen? | ||
- | |||
- | ====== Eingaben ====== | ||
- | |||
- | Wie eingangs beschrieben, | ||
- | Beispiel beim Einwurf von 5Cent den Zustand. Eine //Folge von Aktionen// wird **Eingabe** genannt. | ||
- | |||
- | So sind die Aktionen: | ||
- | |||
- | 5 ct einwerfen – 10 ct einwerfen – 5 ct einwerfen – Knopf drücken – Parkschein entnehmen | ||
- | |||
- | eine Eingabe. | ||
- | |||
- | Ein Automat verarbeitet eine Eingabe, indem er die einzelnen Aktionen der Reihe nach betrachtet und | ||
- | entsprechend reagiert. | ||
- | |||
- | // | ||
- | Zustand ausgeht und mit der Aktion, die an der Reihe ist, beschriftet ist**. | ||
- | |||
- | Eingaben können unterschiedlich aussehen; es können sowohl Folgen von Zahlen, Wörtern, Zeichen | ||
- | oder Buchstaben sein. Bei realen Automaten sind dies Knöpfe, Münzen, Auswahltasten etc. | ||
- | |||
- | Um Automaten strukturiert und übersichtlich darstellen zu können, werden oft Kürzel an den Übergängen verwendet. Diese Standardisierung (Vereinheitlichung) ermöglicht außerdem die Analyse der Eigenschaften von Automaten. Im folgenden Beispiel werden die Übergänge durch Buchstaben abgekürzt: Der folgende Automat | ||
- | hat die Zustände: q1, q2, q3, q4. Der Zustand q1 ist der Startzustand, | ||
- | |||
- | Außerdem hat dieser Automat sechs Übergänge, | ||
- | |||
- | {{ : | ||
- | |||
- | Wie reagiert der Automat | ||
- | |||
- | * Start bei q1. | ||
- | * Wechsel mit '' | ||
- | * Wechsel mit '' | ||
- | * Der Automat bleibt im Zustand q4 mit '' | ||
- | |||
- | Nach der Eingabe '' | ||
- | |||
- | Die Eingabe '' | ||
- | |||
- | === Aufgabe === | ||
- | |||
- | Wie reagiert der Automat oben auf die folgenden Eingaben? | ||
- | |||
- | bbaaa | ||
- | aa | ||
- | aab | ||
- | caaaa | ||
- | |||
- | ===== Eingabealphabet ===== | ||
- | |||
- | Wie bereits erwähnt, können Eingaben sehr unterschiedlich sein. Deswegen ist es nötig, zu jedem Automaten anzugeben, aus welchen Zeichen (z. B. Buchstaben) die Sprache besteht, die er versteht. Die Menge dieser Zeichen wird **Eingabealphabet** genannt. So ist das Eingabealphabet des Automaten aus dem Beispiel oben '' | ||
- | |||
- | <WRAP center round important 60%> | ||
- | Das **Eingabealphabet** eines Automaten ist die Menge an Zeichen (Buchstaben, | ||
- | Zahlen, Wörter, Symbole), auf die der Automat reagieren kann. | ||
- | </ | ||
- | |||
- | |||
- | === Aufgabe === | ||
- | |||
- | {{ : | ||
- | |||
- | Nenne den Startzustand, | ||
- | tomaten. | ||
- | |||
- | Beschreibe außerdem, wie der Automat sich auf die Eingaben 1111, 1100 bzw. | ||
- | 1001 verhält. | ||
- | |||
- | |||