faecher:informatik:oberstufe:automaten:lepro:darstellung:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== 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 Zustand, Übergang und Eingabe von Automaten erläutert. Außerdem wird das Verhalten
von Automaten auf Aktionen genauer betrachtet.

==== Teillernziele ====

Nach der Bearbeitung dieses Kapitels kannst du...

    * unterscheiden, was in der Automatentheorie unter den Begriffen Zustand, Übergang, Eingabe und Reaktion zu verstehen ist.
    * Zustände und Übergänge in exemplarischen, graphischen Darstellungen benennen.
    * 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 "Maschine" vorstellen, die stur einem festgelegten Schema folgt,
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.
</WRAP>

===== Beispiel: Parkscheinautomat =====


Noch einmal zurück zu dem Parkscheinautomaten, vor dem Laura und Manfred stehen:

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:pa01.png?900 |}}

Beschriftet man die Zustände und Übergänge ein wenig anders, sieht das Ganze so aus:

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:pa02.png?600 |}}


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.png?nolink  |}}
=== (A1) ===

 
Eine einfache Supermarktkasse funktioniert folgendermaßen:

  * Wird ein Preis eingegeben, addiert die Kasse diesen zum Gesamtpreis.
  * Drückt jemand die Taste „Kassieren“, wird der Gesamtpreis angezeigt und die Geldlade geöffnet.
  * Wird die Geldlade geschlossen, wartet die Kasse darauf, dass erneut ein Preis eingegeben wird.

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:kasse01.png?600 |}}

Ordne die verschiedenen Zustände der Kasse und die Aktionen des Kassierers/der Kassiererin den Zuständen und Übergängen der Skizze zu. 

Vergleiche die Kasse mit dem Parkautomaten.

====== Besondere Zustände ======

Dir ist vielleicht schon aufgefallen, dass viele Automaten am "ersten" Zustand einen <color green/lightgrey>Pfeil mit der Beschriftung "Start"</color> haben. Dieser Zustand wird auch <color green/lightgrey>**Startzustand**</color> genannt. Komplementär zum Startzustand gibt noch einen weiteren "besonderen" Zustand: den <color green/lightgrey>**Endzustand**</color>. Dieser wird im Allgemeinen durch einen <color green/lightgrey>doppelten Kreis</color> gekennzeichnet. Ein Automat kann auch mehrere Endzustände haben. Auf die besondere Bedeutung von Endzuständen gehen wir später näher ein.

----
{{:aufgabe.png?nolink  |}}
=== (A2) ===


Benenne die Start- und Endzustände der folgenden zwei Automaten:

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:auswahl_728.png?800 |}}

----
{{:aufgabe.png?nolink  |}}
=== (A3) ===

Die Supermarktkasse von oben hat die folgenden Zustände und Übergänge.

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:kasse01.png?600 |}}

Die Kasse hat die folgenden Zustände:
  * q1. Wartezustand; die Kasse wartet auf die Eingabe eines Preises.
  * 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, reagiert ein Automat auf //Aktionen//. So wechselt der Parkscheinautomat zum
Beispiel beim Einwurf von 5Cent den Zustand. <color green/lightgrey>Eine //Folge von Aktionen// wird **Eingabe** genannt</color>. 

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. 

//Reagieren// heißt hier: Der Automat sucht einen //Übergang//, der **vom aktuellen
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, q4 der Endzustand.

Außerdem hat dieser Automat sechs Übergänge, die mit den Buchstaben ''a'', ''b'' und ''c'' markiert sind.

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:automat1.png?600 |}}

Wie reagiert der Automat  auf die Eingabe ''caa''?

  * Start bei q1.
  * Wechsel mit ''c'' von q1 zu q3.
  * Wechsel mit ''a'' von q3 zu q4.
  * Der Automat bleibt im Zustand q4 mit ''a''.

Nach der Eingabe ''caa'' befindet sich der Automat also in dem Zustand q4.

Die Eingabe ''bbb'' hingegen kann der Automat nicht verarbeiten, da es vom Zustand q3 aus keinen Übergang gibt, der mit ''b'' beschriftet ist!
----
{{:aufgabe.png?nolink  |}}
=== (A4) ===


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 ''{a, b, c}''. Das Eingabealphabet muss natürlich nicht aus Buchstaben bestehen, es kann sich auch aus ganzen Wörtern, Sätzen oder Zahlen, Knopfdrücken oder Touchscreengesten zusammensetzen.

<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.
</WRAP>


----
{{:aufgabe.png?nolink  |}}
=== (A5) ===

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:aufgabe1.png?600 |}}

Nenne den Startzustand, den Endzustand und das Eingabealphabet dieses Automaten.

Beschreibe außerdem, wie der Automat sich auf die Eingaben ''1111'', ''1100'' bzw.
''1001'' verhält.

----
{{:aufgabe.png?nolink  |}}
=== (A6) ===


{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:aufgabe2.png?600 |}}

Nenne auch den Startzustand, die Endzustände und das Eingabealphabet dieses Automaten. Beschreibe außerdem das Verhalten des Automaten auf die folgenden drei Eingaben:

  Kartoffelsalat
  Salat
  Nudelsalat

----
{{:aufgabe.png?nolink  |}}
=== (Zusatz-A1) Java ===


In dieser Zusatzaufgabe schreibst du am Computer ein Programm, das einen Automaten simuliert. Das Programm soll ausgeben, in welchem Zustand sich der Automat nach Bearbeitung einer bestimmten Eingabe befindet.

Betrachte erneut den folgenden Automaten:

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:aufgabe1.png?600 |}}

Das Eingabealphabet ist die Menge {0, 1}.

Du sollst nun ein Javaprogramm schreiben, das diesen Automaten simuliert.

Lege dir dazu ein Integer-Array an, in dem die Eingabe gespeichert wird. Die Eingabe kannst
du in dem Programm vorgeben, z. B. durch ''int[] eingabe = {1, 0, 0, 1};''

Dein Programm soll nun ausgeben, in welchem Zustand sich der Automat befindet, nachdem er die Eingabe vollständig abgearbeitet hat.

===== Lernfortschrittskontrolle =====

{{:aufgabe.png?nolink  |}}
=== (L1) ===

Bestimme die Start- und Endzustände des folgenden Automaten

{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:lfk01.png |}}

---- 
{{:aufgabe.png?nolink  |}}
=== (L2) ===

Fülle folgenden Lückentext aus:
<code>
Ein Automat setzt sich aus ____________ und _______________ zusammen. Es gibt un-
terschiedliche Arten von Zuständen. Einer der „besonderen“ Zustände wird mit einem
Pfeil gekennzeichnet; diesen Zustand nennt man _________________________. Ein
weiterer „besonderer“ Zustand wird dagegen mit einem doppelten Kreis gekennzeich-
net; hierbei handelt es sich um den _______________________________.
Ein festgelegtes Schema gibt vor, wann ein Automat von einem _______________ in
einen anderen ________________ übergeht. Allgemein sagt man, dass der Automat
eine _______________ aus dem _____________________ verarbeitet.
</code>

---- 
{{:aufgabe.png?nolink  |}}
=== (L3) ===

Betrachte noch einmal den Automaten der Lernfortschrittskontrolle (L1) oben.

In welchem Zustand befindet sich der Automat nach Bearbeitung der folgenden Eingaben?

  - abcbb
  - abcbcbbb

Setze die folgenden Zeichenketten so fort, dass sich der Automat nach Bearbeitung der Zeichenkette in einem Endzustand befindet. Wähle dabei immer die kürzeste Möglichkeit.

  - a
  - abc
  - abb