Aufgabe Vorschlag C2 - Aufgabe 5 · Abitur Hessen Informatik LK 2021
Thema: Endliche Automaten · 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
5 In Material 3 sehen Sie das Zustandsdiagramm eines endlichen Automaten, der die Sprache L erkennt.
5.1
Begründen Sie, weshalb dieser Automat nichtdeterministisch ist. [2 BE]
5.2
Erläutern Sie das Verfahren der Potenzmengenkonstruktion. [4 BE]
5.3
Überführen Sie das Zustandsdiagramm des Automaten aus Material 3 in das Zustandsdiagramm eines deterministischen endlichen Automaten. Die Potenzmengenbildung soll in der Benennung der Zustände erkennbar werden. [4 BE]
Lösung
Nach den offiziellen Korrekturhinweisen
5.1 Begründen Sie, weshalb dieser Automat nichtdeterministisch ist.
Lösung: Wird im Zustand ein H eingelesen, ist der Übergang nicht eindeutig. Man kann in den Zustand oder in den Zustand gelangen. Aus diesem Grund ist der Automat nichtdeterministisch.
5.2 Erläutern Sie das Verfahren der Potenzmengenkonstruktion.
Lösung: Mit Hilfe der Potenzmengenkonstruktion kann ein nichtdeterministischer endlicher Automat (NEA) nachfolgendem Verfahren in einen deterministischen endlichen Automaten (DEA) transformiert werden: 1. Wähle als Startzustand des DEA den Startzustand des NEA. 2. Konstruiere für jedes Eingabezeichen einen Folgezustand als Menge aller Zustände, die ausgehend vom Startzustand bei Eingabe des Eingabezeichens im NEA erreicht werden können. Füge diesen Übergang hinzu. 3. Füge neu entstandene Zustände zur Zustandsmenge hinzu. 4. Wiederhole ab Schritt 2 für alle neu entstandenen Zustände. 5. Wähle die Menge der Endzustände als diejenige Teilmenge der Zustandsmenge des DEA, deren Mengenzustände einen Endzustand des NEA enthalten.
5.3 Überführen Sie das Zustandsdiagramm des Automaten aus Material 3 in das Zustandsdiagramm eines deterministischen endlichen Automaten. Die Potenzmengenbildung soll in der Benennung der Zustände erkennbar werden.
Lösung: Zustandsdiagramm des resultierenden deterministischen endlichen Automaten (DEA). Bei Eingabe von H aus wird der Zustand erreicht. Von dort führt H nach und F nach . Alle anderen Übergänge bleiben deterministisch.
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 C1 - Aufgabe 1.2 - Endliche Automaten · LK 2021