Aufgabe Vorschlag B2 - 1.2 - Endlicher Automat · 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$

1.2 Entwerfen Sie einen Akzeptor für die Sprache der gültigen Züge des Pferdes. [6 BE]