Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik LK · Haupttermin 2021
Thema: Endliche Automaten · Aus der Prüfung LK · Haupttermin (2021)
Aufgabenstellung
Aufgabenstellung:
Leonard besucht einen Informatikkurs und plant, nach dem Abitur Informatik zu studieren. Beim Aufräumen des Dachbodens, worum ihn seine Eltern gebeten haben, entdeckt er seine alte Modelleisenbahn, mit der er als Kind oft gespielt hat. Dabei fällt ihm ein, dass er früher stets eine sinnvolle Schienenanlage bauen wollte, auf der die Eisenbahn entweder im Kreis fuhr oder an Prellböcken endete. Mit seinem Wissen aus der theoretischen Informatik will Leonard untersuchen, ob eine Schienenanlage sinnvoll aufgebaut ist. Damit die Untersuchung überschaubar bleibt, betrachtet er zunächst nur die folgenden Bauteile.
Ein endlicher Automat soll dazu verwendet werden, zu überprüfen, ob eine Schienenanlage sinnvoll aufgebaut ist.
Hierfür reiht er die Bauteil-IDs zu Wörtern aneinander, die jeweils eine Schienenanlage repräsentieren. Eine Anlage aus zwei Prellböcken mit einer Brücke dazwischen wird zum Beispiel durch das Wort p1b2p beschrieben.
Zur Überprüfung von Schienenanlagen entwirft Leonard einen deterministischen endlichen Automaten A, dessen Zustandsübergangsdiagramm in Abbildung 2 zu sehen ist:
a)
Erläutern Sie, durch welche Eigenschaften sich die Schienenanlagen auszeichnen, die zu den vom Automaten A akzeptierten Wörtern gehören.
Ermitteln Sie sämtliche vom Automaten A akzeptierten Wörter von minimaler Länge, in denen jede Bauteil-ID mindestens einmal vorkommt.
Erläutern Sie, was der Zustand im Sachzusammenhang bedeutet.
b)
Das Wort pp ist Element der Sprache des Automaten A (vgl. Abbildung 2), die zugehörige Schienenanlage ist jedoch nicht sinnvoll.
Begründen Sie im Sachzusammenhang, weshalb die Schienenanlage, die zum Wort pp gehört, nicht sinnvoll ist.
Modifizieren Sie das Zustandsübergangsdiagramm aus Abbildung 2 derart, dass der zugehörige deterministische endliche Automat jedes Wort der Sprache außer dem Wort pp akzeptiert.
Lösung
Nach den offiziellen Korrekturhinweisen
Erläutern Sie, durch welche Eigenschaften sich die Schienenanlagen auszeichnen, die zu den vom Automaten A akzeptierten Wörtern gehören.
Lösung: Die Schienenanlage beginnt und endet mit einem Prellbock. Weitere Prellböcke kommen in der Schienenanlage nicht vor. Nach dem ersten Prellbock können beliebig viele (auch null) gerade Gleise oder Brückenanlagen in beliebiger Reihenfolge folgen, bevor der zweite Prellbock die Schienenanlage beendet. Eine Brückenanlage besteht aus einer Brückenauffahrt und einer Brückenabfahrt. Zwischen Auffahrt und Abfahrt können beliebig viele (auch null) Brückenelemente oder weitere Brückenanlagen liegen.
Ermitteln Sie sämtliche vom Automaten A akzeptierten Wörter von minimaler Länge, in denen jede Bauteil-ID mindestens einmal vorkommt.
Lösung: p1b2gp / pg1b2p
Erläutern Sie, was der Zustand q1 im Sachzusammenhang bedeutet.
Lösung: Im Zustand befindet man sich mitten in einer Schienenanlage auf der unteren Ebene. Die Schienenanlage kann entweder mit Brückenanlagen oder mit geraden Gleisstücken fortgesetzt oder durch einen Prellbock beendet werden.
Begründen Sie im Sachzusammenhang, weshalb die Schienenanlage, die zum Wort pp gehört, nicht sinnvoll ist.
Lösung: Auf diese Schienenanlage könnte man keine Lok und keine Wagen stellen, weil sie nur aus zwei Prellböcken besteht.
Modifizieren Sie das Zustandsübergangsdiagramm aus Abbildung 2 derart, dass der zugehörige deterministische endliche Automat jedes Wort der Sprache LA außer dem Wort pp akzeptiert.
Lösung: Das modifizierte Zustandsübergangsdiagramm führt einen neuen Zustand ein. Vom Zustand gelangt man mit 'g' nach oder mit '1' nach . Vom Zustand aus führen Schleifen mit 'g' zu sich selbst, mit '1' nach und mit 'p' zum Endzustand . Die Rückkehr aus mit '2' führt nach . Vom Zustand gibt es keinen direkten Übergang mit 'p' mehr.
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 4 - Endliche Automaten · GK · Nachtermin 2021 · Aufgabe 4 - Endliche Automaten · LK · Nachtermin 2021 ›
Mehr Aufgaben zu Endliche Automaten
- Aufgabe 4 - Endliche Automaten · LK · Haupttermin 2022
- Aufgabe 4 - Endliche Automaten · LK · Nachtermin 2022
- Aufgabe 4 - Endliche Automaten · GK · Haupttermin 2021
- Aufgabe 4 - Endliche Automaten · GK · Haupttermin · Weiterbildungskolleg 2021
- Aufgabe 4 - Endliche Automaten · GK · Nachtermin 2021
- Aufgabe 4 - Endliche Automaten · LK · Nachtermin 2021