Aufgabe Vorschlag B2 - 3 · Abitur Hessen Informatik GK 2022

Schachfiguren

Die erlaubten Züge einer Schachfigur auf einem Schachbrett können mit den Zeichen n, e, s, w (für north, east, south und west) beschrieben werden.

Schachfiguren bezeichnen wir mit P, T und K (für Pferd, Turm und König).

Das Pferd zieht immer zuerst zwei Felder nach Norden, Süden, Osten oder Westen und anschließend ein Feld senkrecht zu dieser Richtung (siehe Abbildung).

Ein Zug beginnt immer mit dem Zeichen für die Figur, danach folgen ein oder mehrere Zeichen für die Richtung. Zur Vereinfachung muss in keiner Aufgabe berücksichtigt werden, ob eine Schachfigur in einem Zug oder einer Zugfolge das Brett verlässt.

Material 1

Mögliche Züge eines Turms

Material 2

Akzeptor für Zugfolgen des Königs

$\Sigma = \{\text{K, n, s, e, w}\}$

$Z = \{z_0, \dots, z_{13}\}$

Startzustand $z_0$

$E = \{z_2, \dots, z_{13}\}$

$\delta\colon Z \times \Sigma \to Z$ gegeben durch folgende Übergangstabelle:

· K · n · e · s · w

$z_0$ · $z_1$

$z_1$ · · $z_2$ · $z_5$ · $z_8$ · $z_{11}$

$z_2$ · $z_1$ · · $z_3$ · · $z_4$

$z_3$ · $z_1$

$z_4$ · $z_1$

$z_5$ · $z_1$ · $z_6$ · · $z_7$

$z_6$ · $z_1$

$z_7$ · $z_1$

$z_8$ · $z_1$ · · $z_9$ · · $z_{10}$

$z_9$ · $z_1$

$z_{10}$ · $z_1$

$z_{11}$ · $z_1$ · $z_{12}$ · · $z_{13}$

$z_{12}$ · $z_1$

$z_{13}$ · $z_1$

Der endliche Automat in Material 2 akzeptiert gültige Zugfolgen des Königs.

3.1

Erläutern Sie anhand der Übergangstabelle in Material 2 die Zugweise des Königs. (3 BE)

3.2

Begründen Sie anhand eines Beispiels, dass sich die Anzahl der Zustände des Automaten reduzieren lässt. (3 BE)

3.3

Entwickeln Sie aus dem Automaten in Material 2 einen vereinfachten Automaten mit möglichst wenigen Zuständen, indem Sie dessen Übergangstabelle und Zustandsgraphen angeben. (7 BE)