Aufgabe Vorschlag B3 · Abitur Hessen Informatik GK 2022

Thema: Grammatiken, reguläre Ausdrücke und Syntaxdiagramme · Aus der Prüfung GK (2022)

Aufgabenstellung

Olympische Winterspiele

Bei den Olympischen Winterspielen werden einheitlich strukturierte Sportlerdatenlisten angelegt, um Informationen über die Athleten zu speichern. Eine solche Liste beginnt mit dem Namen (n) des Sportlers gefolgt vom Land (l), für das der Sportler antritt. Jeder Sportler nimmt an genau einer Sportart (s) teil, die im Anschluss an das Land gespeichert wird. Wenn ein Sportler bei einer oder mehreren Disziplinen innerhalb einer Sportart zum Wettkampf antritt, stehen im Anschluss eine oder mehrere Disziplinbezeichnungen (d) mit den jeweils erzielten Ergebnissen (e) in den verschiedenen Wettkampfrunden. Die Rundenanzahl ist dabei auf maximal drei begrenzt, eine Runde findet in jedem Fall statt.

Während der Winterspiele werden täglich einige Athleten zufällig ausgewählt, denen eine Dopingprobe entnommen wird. Dabei kann es jeden Athleten mehrfach treffen, einige werden unter Umständen auch gar nicht geprüft. Die Ergebnisse der Dopingproben (p) werden am Ende der Liste gespeichert. Eine Dopingprobe kann positiv oder negativ ausfallen, das Ergebnis steht hinter dem Datum der Durchführung der Dopingprobe, getrennt durch ein Leerzeichen. Eine Beispielsportlerdatenliste mit zugehöriger Listenstruktur befindet sich im Material 1.

Material 1

Beispielsportlerdatenliste mit zugehöriger Listenstruktur

Felix Altreuther

Deutschland

Ski Alpin

Slalom

0:01:57,03

0:01:53,97

Riesenslalom

0:02:14,34

20.02.2018 negativ

22.02.2018 positiv

Die Struktur dieser Liste ist nlsdeedepp.

Material 2

Syntaxdiagramme für Datum

Aufgaben

Die Sprache LL besteht aus den Wörtern, die gültige Strukturen von Sportlerdatenlisten angeben.

1.1

Entscheiden Sie, ob die drei Wörter nls, nlsde und nlsdeedeedeeedpp der Sprache LL angehören. [3 BE]

1.2

Geben Sie zwei weitere Wörter der Sprache LL an, die innerhalb dieser Aufgabe nicht als Wörter der Sprache vorgegeben werden. [1 BE]

2.1

Entwerfen Sie für die Sprache LL eine Grammatik G(L)G(L). [7 BE]

2.2

Geben Sie eine Ableitung des Wortes nlsdeep anhand Ihrer Grammatik G(L)G(L) an. [3 BE]

2.3

Entscheiden Sie, ob Ihre Grammatik G(L)G(L) regulär oder kontextfrei ist. [2 BE]

Aufgabenstellung: Aufgabe Vorschlag B3 · Abitur Hessen Informatik GK 2022

Lösung

Nach den offiziellen Korrekturhinweisen

1.1 Entscheiden Sie, ob das Wort nls der Sprache L angehört.

Lösung: nls ist ein Wort der Sprache L.

1.1 Entscheiden Sie, ob das Wort nlsde der Sprache L angehört.

Lösung: nlsde ist ein Wort der Sprache L.

1.1 Entscheiden Sie, ob das Wort nlsdeedeedeeedpp der Sprache L angehört.

Lösung: nlsdeedeedeeedpp ist kein Wort der Sprache L.

1.2 Geben Sie zwei weitere Wörter der Sprache L an, die innerhalb dieser Aufgabe nicht als Wörter der Sprache vorgegeben werden.

Lösung: nlsdedeep und nlsdee (oder andere gültige Wörter wie nlsdeep, nlsp)

2.1 Entwerfen Sie für die Sprache L eine Grammatik G(L).

Lösung: G(L)=(N,T,P,S)G(L) = (N, T, P, S) mit N={S,A,B,C,D,E,F,G}N = \{S, A, B, C, D, E, F, G\} T={n,l,s,d,e,p}T = \{\text{n}, \text{l}, \text{s}, \text{d}, \text{e}, \text{p}\} Startsymbol = SS P={P = \{ S→nAS \rightarrow \text{n}A, A→lBA \rightarrow \text{l}B, B→sC∣sG∣sB \rightarrow \text{s}C \mid \text{s}G \mid \text{s}, C→dDC \rightarrow \text{d}D, D→eG∣eE∣eC∣eD \rightarrow \text{e}G \mid \text{e}E \mid \text{e}C \mid \text{e}, E→eG∣eF∣eC∣eE \rightarrow \text{e}G \mid \text{e}F \mid \text{e}C \mid \text{e}, F→eG∣eC∣eF \rightarrow \text{e}G \mid \text{e}C \mid \text{e}, G→p∣pG}G \rightarrow \text{p} \mid \text{p}G\}

2.2 Geben Sie eine Ableitung des Wortes nlsdeep anhand Ihrer Grammatik G(L) an.

Lösung: S→nA→nlB→nlsC→nlsdD→nlsdeE→nlsdeeG→nlsdeepS \rightarrow \text{n}A \rightarrow \text{nl}B \rightarrow \text{nls}C \rightarrow \text{nlsd}D \rightarrow \text{nlsde}E \rightarrow \text{nlsdee}G \rightarrow \text{nlsdeep}

2.3 Entscheiden Sie, ob Ihre Grammatik G(L) regulär oder kontextfrei ist.

Lösung: Es handelt sich um eine reguläre Grammatik (und damit auch kontextfreie Grammatik).

Die ausführliche Erklärung Schritt für Schritt (mit KI) gibt es mit Premium. Premium

Löse sie direkt hier: automatische Korrektur, Hinweise und Lösung Schritt für Schritt.

‹ Aufgabe Vorschlag B2 - 2 · GK 2022 · Aufgabe Vorschlag B3 · GK 2022 ›

Mehr Aufgaben zu Grammatiken, reguläre Ausdrücke und Syntaxdiagramme