Aufgabe Vorschlag B2 - 1.1, 1.3-1.5 - Grammatiken und reg… · 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 Den dargestellten Zug (Abbildung) kann man mit Pnnw (Pferd zieht zweimal nach Norden und dann nach Westen) beschreiben. Pees oder Pwws sind ebenfalls gültige Züge. Nach jedem Zug kann ein weiterer Zug mit einer beliebigen Figur stattfinden. Mehrere Züge bilden eine Zugfolge.

1.1

Entscheiden Sie, ob PnnwPsswPeen und PwwnPeesPwwePeen gültige Zugfolgen sind. [3 BE]

1.3

Analysieren Sie die Sprache, die durch folgenden regulären Ausdruck definiert wird: [4 BE]

(P((nn|ss)(e|w)|((ee|ww)(n|s))))+

1.4

Entwerfen Sie eine Grammatik, welche die Sprache der gültigen Zugfolgen für das Pferd erzeugt. [6 BE]

1.5

Geben Sie für Ihre in Aufgabe 1.4 entworfene Grammatik den Ableitungsbaum für das Wort PnnePnnwPeen an. [4 BE]