Aufgabe Vorschlag B2 - 2 · 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$

2 Der Turm (Zeichen T) läuft in einem Zug beliebig viele (mindestens 1 und maximal 7) Felder nach Norden, Süden, Osten oder Westen (Material 1).

Geben Sie einen regulären Ausdruck an, welcher die Sprache der gültigen Zugfolgen der Figuren Pferd und Turm erzeugt.