Folge 29 - kontextfreie Grammatiken: Abitur

4. Abituraufgabe NRW 2007

Wir wollen jetzt mal die Abituraufgaben analysieren, die in den letzten Jahren im Zentralabitur NRW zum Thema "kontextfreie Grammatiken" gestellt worden sind. Beginnen wir mit der Aufgabe aus dem Jahre 2007.

Den Schülern wurde zunächst folgende Sprache für Passworte vorgegeben:

  1. Das Passwort soll aus mindestens 4 Zeichen bestehen.

  2. Das Passwort soll mit mindestens einem Buchstaben beginnen und mit mindestens einem Buchstaben enden.

  3. Das Passwort soll mindestens ein Sonderzeichen und eine Ziffer enthalten.

  4. Die Anzahl der Sonderzeichen und Ziffern muss gleich groß sein.

  5. Sonderzeichen und Ziffern sollen paarweise auftreten, gegebenenfalls mit dazwischenliegenden Buchstaben. Beginnt ein solches Paar mit einem Sonderzeichen, so folgt eine Ziffer, beginnt ein Paar jedoch mit einer Ziffer, so folgt ein Sonderzeichen

In der Hauptaufgabe sollten die Schüler dann einen determinierten endlichen Automaten entwerfen, der Passworte überprüft, ob sie den obigen Regeln entsprechen. Die Modelllösung dazu sah so aus:

Schon ganz schön kompliziert, nicht wahr? Aber schließlich war das auch eine Aufgabe für den Informatik-Leistungskurs. Die Grundkurs-Automaten sind in der Regel wesentlich kleiner. Das Symbol B steht allgemein für Buchstaben, das Symbol Z für Ziffern, und das Symbol S für Sondernzeichen.

Der Arbeitsauftrag, auf den es mir hier ankommt, lautete dann:

"Entwickeln Sie eine Grammatik, die genau die gültigen Passwörter produziert...

Zur Vereinfachung der Grammatik verwenden Sie bitte nur folgende Zeichen:
Buchstaben a, b und c, Ziffern 1, 2 und 3 sowie Sonderzeichen #, § und &."

Hier die offizielle Lösung:

Ich persönlich finde diese Lösung sehr unübersichtlich. Darum habe ich mir mal die Arbeit gemacht, sie Schritt für Schritt zu zerlegen. Zunächst habe ich mal die Bezeichnungen der Nichtterminale geändert, so dass die die jeweiligen Zustände des Automaten repräsentieren:

Jetzt kann man auch erkennen, wie man von dem DEA zur kontextfreien Grammatik kommt, nämlich ganz einfach. Man ersetzt jeden Zustand des DEA durch ein Nichtterminal in der Grammatik.

Die obige Grammatik erscheint mir immer noch zu unhandlich und gleichzeitig ist sie ja auch auf nur drei Buchstaben, drei Ziffern und drei Sondernzeichen begrenzt. Daher habe ich die Grammatik noch etwas vereinfacht:

Einerseits haben wir jetzt wesentlich weniger Regeln, andererseits werden jetzt alle Buchstaben, alle Ziffern und alle Sonderzeichen berücksichtigt.

5. Abituraufgabe NRW 2008

Ich will auch hier nicht die ganze Abituraufgabe besprechen, sondern nur den Teil, der sich auf das Thema "kontextfreie Grammatik" bezieht. Der oben abgebildete DEA soll in eine entsprechende kontextfreie Grammatik umgewandelt werden.

Allerdings sollen die von der Grammatik erzeugten Zeichenketten auf "007" enden. Das heißt, der Zustand S3 des Automaten wird vereinfacht.

Versuchen wir uns doch mal mit dem Verfahren, das sich auch in der letzten Aufgabe bewährt hat. Jeder Zustand des Automaten wird zu einem Nichtterminal.

Nun bin ich ja mal gespannt, wie die offizielle Lösung dieser Aufgabe aussieht.

Die Musterlösung sieht auf den ersten Blick völlig anderes aus als meine Lösung. Aber wenn man näher hinschaut, sieht man, dass die Unterschiede gar nicht so gravierend sind. Wenn man W durch S0, X durch S1 und Y durch S2 ersetzt und dann die Produktionen 1W, 2W, ... , 9W zusammenfasst zu "ziffer W" bzw. "ziffer S0", so decken sich die beiden Grammatiken weitgehend.

Die folgende Zeichenkette ist laut DEA ein gültiges Wort der Sprache L(A):

1445007

Wie könnte man diese Zeichenkette mit der "offiziellen" Grammatik produzieren?

W ===> 1W
1W ===> 14W
14W ===> 144W
144W ===> 1445W
1445W ===> 14450X
14450X ===> 144500Y
144500Y ===> 1445007

O.K., das funktioniert also. Dann wollen wir mal glauben, dass die offizielle Lösung auch korrekt ist.

weiter mit Folge 30: Syntaxanalyse

In dieser Folge wird gezeigt, was ein Parser ist und wie ein Parser nicht nur die Syntax eines Audrucks analysiert, sondern auch gleich den Code für eine Stackmaschine erzeugt.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 20. Februar 2011.





IMPRESSUM