Aufgabe Vorschlag C2 - Aufgabe 4 · Abitur Hessen Informatik LK 2021

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

Aufgabenstellung

Containercodes

In der Containerschifffahrt erhält jeder Container einen weltweit eindeutigen Code aus zehn Zeichen. Die ersten drei Zeichen sind der Reederei-Schlüssel, der aus drei Großbuchstaben besteht. Das vierte Zeichen ist ein Produktgruppenschlüssel, der je nach Art des Containers eines der Zeichen U, J oder Z ist. Die letzten sechs Zeichen stellen die Registriernummer dar, wobei für Zahlen kleiner 100000 die Ziffernfolge vorne mit Nullen aufgefüllt wird. Ein möglicher Containercode ist beispielsweise FTLU006293.

Die letzte Ziffer der Registriernummer ist eine Kontrollziffer. Sie muss so gewählt sein, dass das Ergebnis des folgenden Überprüfungsalgorithmus ein Vielfaches von 10 ist.

Die Großbuchstaben werden anhand der Tabelle in Material 1 durch Zahlen ersetzt. Im Überprüfungsalgorithmus werden dann von links nach rechts die Stellen des Containercodes mit den Zahlen 1 bis 10 multipliziert; die erste Stelle mit 1 und die letzte mit 10. Die Ergebnisse werden aufsummiert und die entstehende Summe ganzzahlig durch 11 geteilt.

Material 1

Tabelle zur Codierung der Buchstaben in Containercodes

A · B · C · D · E · F · G · H · I · J · K · L · M

10 · 12 · 13 · 14 · 15 · 16 · 17 · 18 · 19 · 20 · 21 · 23 · 24

N · O · P · Q · R · S · T · U · V · W · X · Y · Z

25 · 26 · 27 · 28 · 29 · 30 · 31 · 32 · 34 · 35 · 36 · 37 · 38

4 Die Reederei „Hamburg Floyd“ führt für die Verwaltung ihrer Container einen eigenen erweiterten Containercode ein. Dieser Code beginnt mit vier Großbuchstaben, wobei der Reederei-Schlüssel HFL den Anfang oder das Ende dieser vier Zeichen darstellt. Der verbleibende Großbuchstabe des Viererblocks ist beliebig. Dann folgt der Produktgruppen-Schlüssel, ein Bindestrich und abschließend eine natürliche Zahl größer 0, die aus beliebig vielen Ziffern bestehen kann, wobei keine führenden Nullen vorkommen dürfen. Die Sprache der Erweiterungscodes bezeichnen wir mit L.

4.1

Geben Sie eine Grammatik für die Sprache L an. [3 BE]

4.2

Ordnen Sie Ihre Grammatik G(L) sowie die Sprache L begründet in die Chomsky-Hierarchie ein. [2 BE]

4.3

Geben Sie bezogen auf Ihre Grammatik einen Ableitungsbaum oder eine Ableitung für den Erweiterungscode AHFLZ-14 an. [2 BE]

4.4

Erläutern Sie, weshalb das Syntaxdiagramm in Material 2 die Sprache L nicht korrekt darstellt. [1 BE]

Aufgabenstellung: Aufgabe Vorschlag C2 - Aufgabe 4 · Abitur Hessen Informatik LK 2021

Lösung

Nach den offiziellen Korrekturhinweisen

4.1 Geben Sie eine Grammatik für die Sprache L an.

Lösung: T={A..Z,0..9,−}T = \{\mathrm{A..Z}, 0..9, -\} N={Code,Bst,Nat,Zif,Schl}N = \{\mathrm{Code}, \mathrm{Bst}, \mathrm{Nat}, \mathrm{Zif}, \mathrm{Schl}\} S=CodeS = \mathrm{Code} P={P = \{ Code→H F L Bst Schl − Nat∣Bst H F L Schl − Nat,\mathrm{Code} \rightarrow \mathrm{H}\ \mathrm{F}\ \mathrm{L}\ \mathrm{Bst}\ \mathrm{Schl}\ -\ \mathrm{Nat} \mid \mathrm{Bst}\ \mathrm{H}\ \mathrm{F}\ \mathrm{L}\ \mathrm{Schl}\ -\ \mathrm{Nat}, Bst→A∣B∣⋯∣Z,\mathrm{Bst} \rightarrow \mathrm{A} \mid \mathrm{B} \mid \dots \mid \mathrm{Z}, Schl→U∣J∣Z,\mathrm{Schl} \rightarrow \mathrm{U} \mid \mathrm{J} \mid \mathrm{Z}, Nat→1∣2∣⋯∣9∣1Zif∣2Zif∣⋯∣9Zif,\mathrm{Nat} \rightarrow 1 \mid 2 \mid \dots \mid 9 \mid 1\mathrm{Zif} \mid 2\mathrm{Zif} \mid \dots \mid 9\mathrm{Zif}, $\mathrm{Zif} \rightarrow 0 \mid 1 \mid \dots \mid 9 \mid 0\mathrm{Zif} \mid 1\mathrm{Zif} \mid \dots \mid 9\mathrm{Zif} \}$

4.2 Ordnen Sie Ihre Grammatik G(L) sowie die Sprache L begründet in die Chomsky-Hierarchie ein.

Lösung: Grammatik: Chomsky-Typ 2 (kontextfrei). Sprache L: Chomsky-Typ 3 (regulär).

4.3 Geben Sie bezogen auf Ihre Grammatik einen Ableitungsbaum oder eine Ableitung für den Erweiterungscode AHFLZ-14 an.

Lösung: alternativ als Ableitung: Code→Bst H F L Schl − Nat→A H F L Schl − Nat→A H F L Z − Nat→A H F L Z − 1 Zif→A H F L Z − 1 4\mathrm{Code} \rightarrow \mathrm{Bst}\ \mathrm{H}\ \mathrm{F}\ \mathrm{L}\ \mathrm{Schl}\ -\ \mathrm{Nat} \rightarrow \mathrm{A}\ \mathrm{H}\ \mathrm{F}\ \mathrm{L}\ \mathrm{Schl}\ -\ \mathrm{Nat} \rightarrow \mathrm{A}\ \mathrm{H}\ \mathrm{F}\ \mathrm{L}\ \mathrm{Z}\ -\ \mathrm{Nat} \rightarrow \mathrm{A}\ \mathrm{H}\ \mathrm{F}\ \mathrm{L}\ \mathrm{Z}\ -\ 1\ \mathrm{Zif} \rightarrow \mathrm{A}\ \mathrm{H}\ \mathrm{F}\ \mathrm{L}\ \mathrm{Z}\ -\ 1\ 4

4.4 Erläutern Sie, weshalb das Syntaxdiagramm in Material 2 die Sprache L nicht korrekt darstellt.

Lösung: Sowohl vor als auch hinter der Zeichenkette HFL ist ein beliebiger Buchstabe möglich. Somit können sowohl Wörter mit sechs Buchstaben zu Beginn als auch vier Buchstaben zu Beginn erzeugt werden. Beides ist in der Sprache nicht erlaubt.

4.3 Geben Sie bezogen auf Ihre Grammatik einen Ableitungsbaum oder eine Ableitung für den Erweiterungscode AHFLZ-14 an.

Lösung: Wurzel S verzweigt zu R P '-' N. R verzweigt zu B 'H' 'F' 'L', B verzweigt zu 'A'. P verzweigt zu 'Z'. N verzweigt zu Z_nz F, Z_nz verzweigt zu '1', F verzweigt zu Z, Z verzweigt zu '4'.

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 C2 - Aufgabe 2 · LK 2021

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