2020: Elektrische Schaltungen

Aufgabenstellung

In dieser Aufgabe geht es um einfachste elektrische Schaltungen, die nur aus Widerständen bestehen, die in Reihe oder parallel geschaltet sind. In einer solchen Schaltung können Reihen- und Parallelschaltungen gleichzeitig und jeweils mehrmals vorkommen. Das folgende Bild zeigt zum Beispiel

eine Schaltung aus fünf Widerständen. Die beiden ersten Widerstände sind hintereinander geschaltet, also in Reihe. Dann verzweigt sich die Schaltung. Im oberen Zweig haben wir nur einen Widerstand, im unteren Zweigt sind zwei Widerstände in Reihe geschaltet. Danach vereinigen sich die Leitungen wieder, und die Schaltung ist beendet.

Die zentrale Frage in dieser Abiturklausur von 2020 ist die Folgende: Wie kann man soche Schaltungen mit Hilfe von Endlichen Automaten oder Regulären Grammatiken formulieren, so dass man nicht ständig Zeichnungen der Schaltungen anfertigen muss?

Umsetzung als Determinierter endlicher Automat

Die Sprache dieses DEAs besteht aus folgenden Worten:

• w = Widerstand
• p = Beginn einer Parallelschaltung
• e = Ende einer Parallelschaltung
• t = Trennzeichen zwischen parallelen Zweigen in einer Parallelschaltung

Die Schaltung aus der obigen Abbildung könnte dann so geschrieben werden:

wwpwtwwe

• Zunächst kommen zwei Widerstände hintereinander: ww
• Dann beginnt eine Parallelschaltung: p
• Nun kommt der obere Zweig der Parallelschaltung: w
• Das Trennzeichen signalisiert, dass die obere Parallelschaltung abgeschlossen ist: t
• Jetzt kommt die untere Parallelschaltung: ww
• Schließlich ist das Ende der Parallelschaltung erreicht: e

Zusammengefasst also: wwpwtwwe

In der Aufgabe wird den Kandidaten männlichen, weiblichen und diversen Geschlechts dann die Zeichnung eines Nichtdeteriministischen endlichen Automaten A₁ präsentiert, der genau diese Schaltungen akzeptiert.

Aufgabe 1

Den Kandidaten wird eine weitere einfache Schaltung präsentiert, und sie müssen die Schaltungscodierung angeben, die dieser Schaltung entspricht. Das ist eine noch recht einfache Aufgabe.

Dann sollen die K. eine Zustandsfolge des Automaten angeben, die zum Akzeptieren einer bestimmten Schaltungscodierung führt.

Als Nächstes sollen die K. beweisen, dass A₁ eine bestimmte zweite Schaltungscodierung nicht akzeptiert.

Schließlich sollen die K. eine Schaltungscodierung angeben, die zwei Parallelschaltungen enthält.

Aufgabe 2

Hier sollen die S. eine reguläre Grammatik entwickeln, die exakt die gleiche Sprache hat wie der vorgestellte NDEA. Nachdem sie erläutert haben, wieso es sich bei dieser Grammatik um eine reguläre Grammatik handelt, sollen die S. zeigen, dass sich eine bestimmte vorgegebene Codierung mit der entwickelten Grammatik erzeugen lässt.

Aufgabe 3

Hier erhalten die K. eine neue Grammatik G₂ für die Beschreibung von Schaltungen. Die K. sollen G₂ nun analysieren, ein Wort angeben, dass mit G₂ erzeugt werden kann, aber nicht von A₁ akzeptiert wird, ein Wort angeben, das von A₁ akzeptiert wird, aber nicht von G₂ erzeugt werden kann, und schließlich ein Wort angeben, das sowohl von G₂ erzeugt werden kann wie auch von A₁akzeptiert wird.

Aufgabe 4

Jetzt wird es langsam kompliziert. Die Schaltungen sollen jetzt nämlich in den Zweigen einer Parallelschaltung weitere Parallelschaltungen enthalten können, sogenannte "innere Parallelschaltungen". Diese inneren Parallelschaltungen sollen dann aber keine weiteren Parallelschaltungen enthalten können, die Verschachtelungstiefe ist also 2 und damit endlich.

Die K. sollen nun den Automaten A₁ so erweitern, dass auch solche Schaltungen akzeptiert werden, und sie sollen die Schaltungscodierung angeben, die einem vorgegebenen Schaltungsdiagramm entspricht, dass eine innere Parallelschaltung enthält.

Aufgabe 5

Es wäre schön, wenn die Schachtelungstiefe der Schaltungen nicht begrenzt wäre. Die K. sollen nun beurteilen, ob es eine reguläre Grammatik gibt, die solche Schaltungscodierungen erzeugen kann.

Bemerkung: Diese Aufgabe ist recht schnell zu lösen. Eine reguläre Grammatik kann immer durch einen endlichen Automaten dargestellt werden, und endliche Automaten können bekanntlich nicht zählen, dazu benötig man einen Stackautomaten bzw. Kellerautomaten. Solche Automaten können zählen, lassen sich aber nicht mehr in einer einfache reguläre Grammatik überführen, sondern können nur durch eine kontextfreie Grammatik dargestellt werden.