MV Abitur Computer Science: Ticketcodes, Ziffernsumme und die Frage nach dem Kellerautomaten

Ticketcodes, Ziffernsumme und die Frage nach dem Kellerautomaten

Für das Schulfest schreibt der Leistungskurs ein Ticketsystem. Ein Code hat die Form MV- + vier Ziffern + ein Großbuchstabe, ist also immer 8 Zeichen lang, zum Beispiel MV-4821K. Zusätzlich gilt: Die Summe der vier Ziffern muss durch 3 teilbar sein, sonst ist der Code ungültig. Ein Kursmitglied behauptet: „Weil man eine Summe prüfen muss, brauchen wir einen Kellerautomaten – ein endlicher Automat kann sich nichts merken.“ Ein zweites Feld enthält Sitzplatzblöcke in Klammern, etwa ((A)) oder (B); jede öffnende Klammer muss genau eine schließende haben, und die Schachtelung darf beliebig tief sein. Der bereits produktiv eingesetzte Ausdruck ^MV-(\d{4})([A-Z])$ akzeptiert die Ziffernsummenregel nicht. Vor der Abnahme soll der Kurs begründen, welche Modelle für welches Feld angemessen sind – und ob der Regex einfach erweitert werden kann.

1. Widerlegen Sie die Behauptung, für die Ziffernsummenregel sei ein Kellerautomat nötig, und geben Sie einen endlichen Automaten an.

Read the worked answer

Widerlegung: Die Behauptung verwechselt zwei Arten von „Erinnern“. Unbegrenztes Zählen (etwa „gleich viele a wie b, beliebig viele“) braucht einen Stack. Hier ist die zu merkende Information dagegen endlich: Ob eine Zahl durch 3 teilbar ist, hängt nur vom Rest modulo 3 ab, und davon gibt es drei Möglichkeiten.

Konstruktion (DEA): Zustände q0, q1, q2 für den Rest der bisher gelesenen Ziffernsumme modulo 3, Startzustand q0.

Präfix M, V, -: feste Übergänge bis zum Ziffernteil.
Für jede Ziffer d: Übergang q_r --d--> q_{(r+d) mod 3}.
Nach genau vier Ziffern: nur aus q0 mit einem Großbuchstaben A–Z in den einzigen Endzustand; aus q1 und q2 gibt es keinen akzeptierenden Übergang.

Beispiel MV-4821K: 4+8+2+1 = 15, 15 mod 3 = 0 → akzeptiert. MV-4822K: 16 mod 3 = 1 → abgelehnt.

Zusatzargument: Die gesamte Codesprache ist sogar endlich (10.000 Ziffernkombinationen × 26 Buchstaben = 260.000 Wörter). Jede endliche Sprache ist regulär – ein Kellerautomat wäre hier in jedem Fall überdimensioniert.

Fazit: Der Automat braucht drei Zustände, nicht einen Stack. Die Aussage „ein endlicher Automat kann sich nichts merken“ ist falsch; richtig ist: Er kann sich nur endlich viel merken.

2. Zeigen Sie mit dem Pumping-Lemma, dass die Sprache der korrekt geklammerten Sitzplatzblöcke bei unbegrenzter Schachtelung nicht regulär ist. Gehen Sie anschließend darauf ein, was die praktische Tiefenbegrenzung auf 20 Ebenen für die Antwort bedeutet.

Read the worked answer

Behauptung: L = { w über { (, ) } | jede öffnende Klammer hat genau eine schließende, korrekte Schachtelung } ist nicht regulär.

Beweis (Pumping-Lemma für reguläre Sprachen): Angenommen, L sei regulär mit Pumping-Länge p.

Wähle w = (^p )^p. Es gilt w ∈ L und |w| = 2p ≥ p.
Nach dem Lemma gibt es eine Zerlegung w = xyz mit |xy| ≤ p, |y| ≥ 1, und x y^i z ∈ L für alle i ≥ 0.
Wegen |xy| ≤ p liegt y vollständig im ersten Block, besteht also nur aus öffnenden Klammern: y = (^k mit k ≥ 1.
Pumpe mit i = 2: x y² z enthält p+k öffnende, aber nur p schließende Klammern. Die Anzahl stimmt nicht mehr, also ist x y² z ∉ L – Widerspruch.

Damit ist L nicht regulär; ein Kellerautomat (oder eine kontextfreie Grammatik) ist das passende Modell, weil die Anzahl unbegrenzt ist und der Stack sie zählt.

Bedeutung der Tiefenbegrenzung: Implementiert das System hart maximal 20 Ebenen, ist die tatsächlich akzeptierte Sprache endlich – und damit regulär. Theoretisch und praktisch fallen die Antworten also auseinander. Für die Abnahme heißt das: Wenn die Grenze garantiert und geprüft wird (Eingabevalidierung, Konfiguration unveränderlich), genügt ein DEA mit endlich vielen Zuständen. Soll die Grenze später erhöht werden oder ist sie nur eine Konvention, ist der Kellerautomat die robustere Wahl – die Antwort hängt an einer Designentscheidung, nicht an der Grammatik allein.

3. Beurteilen Sie, ob der vorhandene Ausdruck `^MV-(\d{4})([A-Z])$` um die Ziffernsummenregel erweitert werden sollte. Geben Sie eine Empfehlung mit Begründung.

Read the worked answer

Theoretisch ja: Die Sprache ist endlich, also regulär, also durch einen regulären Ausdruck beschreibbar. Man könnte alle rund 3.300 vierstelligen Ziffernfolgen mit durch 3 teilbarer Quersumme als Alternative auflisten.

Praktisch nein – vier Gründe:

Wartbarkeit: Ein Ausdruck mit Tausenden Alternativen ist nicht lesbar, nicht prüfbar und nicht wartbar. Kein Kursmitglied könnte Fehler darin finden.
Fehlerrisiko: Beim Aufzählen von Hand schleichen sich Auslassungen ein; das Ergebnis wäre still falsch, genau wie bei den übersehenen Preiszeilen in einer redundant geführten Tabelle.
Nicht offensichtlich korrekt: Ein Regex beschreibt die Sprache, erklärt sie aber nicht. Die Idee „Rest modulo 3“ ist im Code in drei Zeilen nachvollziehbar; im Ausdruck ist sie verschwunden.
Konkreter Fehler im vorhandenen Ausdruck: \d bedeutet in Java (und in vielen Engines) „Unicode-Ziffer“, nicht [0-9]. Ein arabisch-indisches Ziffernzeichen würde akzeptiert. Für ein Ticket ist das falsch; korrekt wäre [0-9]{4}.

Empfehlung: Zweistufig prüfen.

Struktur weiterhin mit einem schlanken Ausdruck ^MV-([0-9]{4})([A-Z])$ – das ist genau seine Stärke.
Quersumme im Code über einen Modulo-3-Zähler (oder einen DEA mit drei Zuständen) prüfen, mit Einzeltests für alle Reste.

Einordnung: Der Regex ist kein Ersatz für den Automaten, sondern eine Kurzschreibweise für einfache reguläre Sprachen. Sobald eine Rechenregel dazukommt, ist der Code das klarere Werkzeug – auch wenn beide Modelle dieselbe Sprache beschreiben.