Wichtige Inhalte zum Thema "Formale Sprachen, Automaten, Grammatiken"
Im Zentralabitur NRW wird von den Kandidaten männlichen, weiblichen und diversen Geschlechts immer wieder verlangt, dass man Diagramme von determinierten oder auch von nichtdeterminierten endlichen Automaten analysieren und damit arbeiten kann. Die Sprache eines solchen Automaten sollte definiert werden können, und vorgegebene Worte sollen überprüft werden, ob sie zur Sprache des Automaten gehören, indem die Zustandsfolge angegeben wird, welche der Automat beim Analysieren durchläuft.
Dann sollten die Kandidaten auch in der Lage sein, einen vorgegebenen Automaten um bestimmte Features zu erweitern, das ist schon etwas schwieriger, aber immer noch einigermaßen leicht zu schaffen.
Jetzt wird es langsam schwieriger. Selbstverständlich sollten die Kandidaten auch in der Lage sein, einen komplett neuen Automaten nach einer vorgegebenen Problemstellung zu entwerfen und die Übergangsfunktion zu zeichnen oder auch in Form einer Tabelle darzustellen.
Und schließlich, das ist das Zweit-Schwierigste, sollten die Kandidaten einen endlichen Automaten in eine äquivalente reguläre Grammatik überführen können und in der Lage sein, diese Grammatik auch noch um weitere Features zu erweitern.
Und jetzt kommt das Schwierigste: Leider gibt es auch Aufgaben, die von den Kandidaten verlangen, eine neue reguläre Grammatik nach bestimmten Vorgaben zu entwickeln, ohne dass ihnen ein endlicher Automat vorgegeben wird.
Schauen wir uns dazu doch einmal die entsprechende Abituraufgabe von 2020 an.