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

Sachkontext: Signalprotokolle im SETI-Projekt

Radioteleskope gehören zu den zentralen Instrumenten der heutigen Astronomie. Mithilfe großer Antennen erfassen sie Signale im Frequenzbereich von 0.01 GHz und 100.00 GHz und stellen diese Daten vielen Forschungsprojekten zur Verfügung. Eines davon ist das SETI-Projekt (Search for Extraterrestrial Intelligence), das untersucht, ob einige der empfangenen Radiosignale von außerirdischen Zivilisationen stammen könnten, die Kontakt aufnehmen wollen.

So könnte ein einfaches Frequenz-Signalprotokoll aussehen:

43.22;0.10;3.21;1.53;14.22 Das Protokoll entsteht, indem einmal pro Sekunde ein neuer Eintrag mit dem jeweils stärksten Signal durch ein Semikolon abgetrennt ergänzt wird. Wird ein Signal empfangen, so wird die Frequenz auf zwei Nachkommastellen genau angefügt. Wird kein Signal empfangen, wird 0.00 angefügt. Signalprotokolle können prinzipiell beliebig lang sein.

Beim SETI-Projekt sucht man in Signalprotokollen in erster Linie nach Frequenzen zwischen einschließlich 1.42 GHz und einschließlich 1.66 GHz, dem sogenannten Wasserloch. In diesem Frequenzbereich existieren besonders wenig störende natürliche Signale, so dass man davon ausgeht, dass eine außerirdische Zivilisation diesen Frequenzbereich zur Kontaktaufnahme nutzen würde.

Obwohl der Wasserloch-Frequenzbereich relativ wenig natürliche Störquellen beinhaltet, kommt es immer wieder zu künstlichen Störsignalen, die in der Umgebung des Radioteleskops durch technische Geräte (z. B. Mikrowellenöfen) entstehen. Im Verhältnis zu Signalen, die aus großer Entfernung zu uns kommen, sind diese Störsignale meist sehr energiereich, so dass man sie oft anhand der Signalstärke identifizieren kann.

Beim SETI-Projekt beschließt man daher, in Zukunft mit einem erweiterten Signalprotokoll zu arbeiten, in dem neben der Frequenz auch die Signalstärke verzeichnet ist. Ein solches erweitertes Signalprotokoll könnte wie folgt aussehen:

(43.22:2);(0.10:1);(3.21:4);(0.00:0);(1.53:b);(14.22:9) Hinter jedem Frequenzeintrag steht nun durch einen Doppelpunkt abgetrennt die Stärke des Signals in den Stufen

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f

wobei 1 für ein sehr schwaches und f für ein sehr starkes Signal steht. Die Signalstärke 0 wird eingetragen, wenn kein Signal aufgefangen wurde. Darüber hinaus wird jeder so erweiterte Frequenzeintrag in Klammern gesetzt.

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.

Dokumentation der Klasse Protokollpruefer Protokollpruefer()

Das Objekt der Klasse Protokollpruefer wird initialisiert.

List<Signal> ermittleMoeglicheKontakte(List<Signal> pProtokoll)

Die Methode liefert eine Liste aller Signaleinträge aus dem Signalprotokoll pProtokoll, deren Frequenzen zwischen einschließlich 1.42 GHz und einschließlich 1.66 GHz liegen und die Signalstärke 1 oder 2 haben.

Die Klasse Signal

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

Dokumentation der Klasse Signal 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

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.

Dokumentation der Klasse List<ContentType> 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 gibt (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.

a)

Wenn Signalprotokolle übertragen werden, treten oft Fehler auf, welche die spätere Auswertung erschweren. Deshalb wird die Korrektheit der Protokolle überprüft. Hierfür dient der Automat $A_1$, dessen Zustandsübergangsdiagramm Abbildung 1 zeigt. Seine Aufgabe erfüllt er allerdings 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.

[9 Punkte]

b)

Im SETI-Projekt werden Signalprotokolle vor allem auf Frequenzen von $1.42\text{ GHz}$ bis einschließlich $1.66\text{ GHz}$ untersucht, das sogenannte Wasserloch (Grenzen eingeschlossen). Da es dort besonders wenige natürliche Störsignale gibt, vermutet man, dass eine außerirdische Zivilisation diesen Bereich für die Kontaktaufnahme wählen 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 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.

[14 Punkte]