Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik GK · Haupttermin 2022

Sachkontext: Signalprotokolle für das SETI-Projekt

In der modernen Astronomie spielen Radioteleskope eine zentrale Rolle. Über große Antennen erfassen sie Signale im Frequenzbereich von 0.01 GHz bis 100.00 GHz und stellen die Daten vielen Forschungsprojekten zur Verfügung. Zu diesen gehört das SETI-Projekt (Search for Extraterrestrial Intelligence), das der Frage nachgeht, ob einige der empfangenen Radiosignale von außerirdischen Zivilisationen stammen könnten, die Kontakt aufnehmen wollen.

Ein einfaches Protokoll der Signalfrequenzen kann etwa so aussehen:

43.22;0.10;3.21;1.53;14.22

Jede Sekunde wird dem Protokoll, durch ein Semikolon getrennt, ein neuer Eintrag für das stärkste Signal hinzugefügt. Bei einem empfangenen Signal wird dessen Frequenz mit zwei Nachkommastellen eingetragen. Wurde kein Signal empfangen, wird 0.00 eingetragen. Prinzipiell kann ein Signalprotokoll beliebig lang werden.

Das Wasserloch

Im SETI-Projekt achtet man in den Signalprotokollen vor allem auf Frequenzen von 1.42 GHz bis 1.66 GHz (jeweils einschließlich), das sogenannte Wasserloch. Hier gibt es besonders wenige natürliche Störsignale, weshalb man annimmt, dass eine außerirdische Zivilisation diesen Bereich für eine Kontaktaufnahme wählen würde.

Erweitertes Signalprotokoll

Auch wenn das Wasserloch nur wenige natürliche Störquellen aufweist, treten dort wiederholt künstliche Störsignale auf, die von technischen Geräten (z. B. Mikrowellenöfen) in der Nähe des Radioteleskops erzeugt werden. Verglichen mit Signalen aus weiter Ferne sind sie meist sehr energiereich und lassen sich daher häufig an ihrer Signalstärke erkennen.

Deshalb entscheidet man sich im SETI-Projekt, künftig ein erweitertes Signalprotokoll zu verwenden, das zusätzlich zur Frequenz die Signalstärke festhält. Ein erweitertes Signalprotokoll kann zum Beispiel so aussehen:

(43.22:b);(0.10:a);(3.21:d);(0.01:a);(1.53:b);(14.22:f)

Nach jeder Frequenz folgt nun, durch einen Doppelpunkt getrennt, die Signalstärke mit den Stufen

a, b, c, d, e, f

Dabei steht a für ein sehr schwaches und f für ein sehr starkes Signal. Zudem wird jeder derart erweiterte Eintrag von Klammern umschlossen.

Anhang: Dokumentation der Klassen

Die Klasse Protokollpruefer

Ein Objekt der Klasse Protokollpruefer wird verwendet, um erweiterte Signalprotokolle auf eventuelle Kontaktversuche von außerirdischen Zivilisationen zu überprüfen.

Methode · Beschreibung

Protokollpruefer()

Das Objekt der Klasse Protokollpruefer wird initialisiert.

boolean enthaeltSchwachesSignal(List<Signal> pProtokoll)

Die Methode liefert den Wert true, wenn das übergebene erweiterte Signalprotokoll pProtokoll mindestens einen Eintrag enthält, der die Signalstärke a oder b hat. Ansonsten liefert die Methode den Wert false.

Die Klasse Signal

Ein Objekt der Klasse Signal speichert einen einzelnen Signaleintrag bestehend aus einer Signalfrequenz und einer Signalstärke.

Methode · Beschreibung

Signal(double pFrequenz, char pStaerke)

Das Objekt der Klasse Signal wird mit pFrequenz als Signalfrequenz und pStaerke als Signalstärke initialisiert.

double gibFrequenz()

Die Methode liefert die Signalfrequenz des Eintrags.

char gibStaerke()

Die Methode liefert die Signalstärke des Eintrags.

Die generische Klasse List<ContentType>

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Methode · Beschreibung

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

Teilaufgabe a)

Werden Signalprotokolle übertragen, treten oft Fehler auf, welche die spätere Auswertung erschweren. Deshalb prüft man die Protokolle auf ihre Korrektheit. Dazu dient der Automat $A_1$, dessen Zustandsübergangsdiagramm in Abbildung 1 dargestellt ist. Diese Prüfung leistet er jedoch nur zum Teil.

Geben Sie für den Automaten $A_1$ den Startzustand, die Endzustände, das Eingabealphabet und die Zustandsmenge an.

Analysieren Sie den Automaten $A_1$ und erläutern Sie, welchen Aufbau eine Eingabezeichenfolge haben muss, damit sie als fehlerfrei akzeptiert wird.

Ermitteln Sie eine Zeichenfolge, die der Automat $A_1$ akzeptiert, obwohl sie kein korrektes Signalprotokoll ist.

Teilaufgabe b)

Im SETI-Projekt werden Signalprotokolle vor allem auf Frequenzen von $1.42\text{ GHz}$ bis $1.66\text{ GHz}$ (jeweils einschließlich) untersucht, das sogenannte Wasserloch. Dort gibt es besonders wenige störende natürliche Signale; deshalb nimmt man an, dass eine außerirdische Zivilisation diesen Bereich für die Kontaktaufnahme verwenden würde.

Ein Mitarbeiter hat die Idee, auch für die inhaltliche Auswertung einen Automaten zur Hilfe zu nehmen. Der nichtdeterministische endliche Automat $A_2$ soll von allen einfachen Signalprotokollen diejenigen akzeptieren, in denen mindestens ein Signal im Wasserloch-Frequenzbereich enthalten ist. Die formale Korrektheit des Protokolls kann vorausgesetzt werden, so dass sie vom Automaten $A_2$ nicht überprüft werden muss.

Entwerfen Sie den nichtdeterministischen endlichen Automaten $A_2$ gemäß den oben genannten Anforderungen.

Begründen Sie, warum Ihr Automat $A_2$ ein nichtdeterministischer endlicher Automat (NEA) ist.

Zeigen Sie, dass das Signalprotokoll 9.01;1.52;0.00 von Ihrem Automaten $A_2$ akzeptiert wird.