Modelleisenbahnen
In dieser Abituraufgabe aus dem Gebiet "formale Sprachen" geht es um das Bauen einfacher Eisenbahnanlagen mit wenigen Elementen wie geraden und gebogenen Gleisen, Brückenauf- und -abfahrten, Brückenelementen und Prellböcken. Die Regeln zur Anordnung dieser Elemente werden durch einen determinierten endlichen Automaten vorgegeben und sollen mit Hilfe einer regulären Grammatik erweitert werden.
Die Abituraufgabe, näher betrachtet
In der ersten Teilaufgabe wird den Kandidaten (m/w/d) ein Determinierter endlicher Automat vorgestellt, mit dem geprüft werden kann, ob eine Schienenanlage aus
- geraden Gleisstücken (g)
- Brückenauffahrten (1)
- Brückenabfahrten (2)
- Brückenelementen (b)
- Prellböcken (p)
sinnvoll aufgebaut ist. Die Kandidaten sollen den Automaten analysieren und testen.
In der zweiten Teilaufgabe soll begründet werden, warum die Schienenanlage pp zwar vom Automaten akzeptiert wird, aber keinen Sinn macht. Anschließend soll der vorgegebene Automaten so verändert werden, dass das Wort pp nicht mehr akzeptiert wird.
In der dritten Teilaufgabe werden die Brückenauf- und -abfahrten und die Brückenelemente durch Rechtskurven (r) und Linkskurven (l) ersetzt. Dann wird den Kandidaten eine Grammatik G vorgestellt, die Produktionen wie zum Beispiel S -> pKp enthält. Die Kandidaten sollen jetzt Worte auflisten, die zu dieser Grammatik gehören, analysieren, welche Schienenanlagen durch die Grammatik dargestellt werden, begründen, warum die Grammatik nicht regulär ist und schließlich eine reguläre Grammatik für die gleiche Sprache entwickeln.
In der vierten Teilaufgabe sollen die Kandidaten beurteilen, ob es möglich ist, einen DEA zu konstruieren, der erkennt, ob eine Schienenanlage aus beliebig vielen geraden Gleisstücken und Kurven ein Oval darstellt.
In der letzten Teilaufgabe soll eine Java-Methode implementiert werden, die ein Objekt der Klasse List zurückliefert. In dieser Liste sollen alle möglichen Gleisanlagen mit gültigen Ovalen gespeichert werden. Dabei wird die maximale Zahl gerade Gleisstücke durch einen Parameter pMax vorgegeben.