Aufgabe 4 - Grammatiken und Kellerautomaten · Abitur NRW Informatik LK · Haupttermin 2022

Thema: Grammatiken, Kellerautomaten und Grenzen endlicher Automaten · Aus der Prüfung LK · Haupttermin (2022)

Aufgabenstellung

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.

Teilaufgabe c)

Die Sprache der erweiterten Signalprotokolle wird durch die nachstehende Grammatik $G_1$ erzeugt.

Startsymbol: $S$

Terminalsymbole: $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, (,),.,:,;\}$

Nichtterminalsymbole: $\{S, F, I, N, Z, B\}$

Produktionen:

S → F:I | F:I;S,

F → (ZN.NN,

I → N) | B),

N → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,

Z → ε | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,

B → a | b | c | d | e | f

c.1

Erläutern Sie die Produktionen der Grammatik $G_1$ . [5 Punkte]

c.2

Begründen Sie, weshalb die Grammatik $G_1$ nicht zu den regulären Grammatiken gehört. [3 Punkte]

c.3

Begründen Sie, weshalb die Sprache, die die Grammatik $G_1$ erzeugt, regulär ist. [4 Punkte]

Teilaufgabe e)

Bald zeigt sich, dass die Signalstärke Störsignale nicht zuverlässig erkennen lässt. Auch Störsignale können schwach sein, und möglicherweise werden Kontaktversuche von Außerirdischen mit sehr hoher Energie gesendet.

Deshalb will das SETI-Projekt künftig anders vorgehen und zusätzlich ein Radioteleskop in Nordafrika nutzen. Wegen der abgelegenen Lage erhofft man sich dort weniger Störsignale.

Um das zu überprüfen, wird ein Protokoll aus Nordafrika, durch ein Ausrufezeichen ( !) abgetrennt, an ein Protokoll aus Europa angefügt. Beide Protokolle müssen genau denselben Zeitraum abdecken.

Beispiel:

3.21;0.00;1.53;14.22 (Europa)

64.22;0.12;1.53;23.11 (Nordafrika)

3.21;0.00;1.53;14.22!64.22;0.12;1.53;23.11 (kombiniert)

Ein Kellerautomat soll nun feststellen, ob der Eintrag 0.00 im Protokoll aus Nordafrika häufiger vorkommt als im Protokoll aus Europa, der afrikanische Standort also &bdquo;ruhiger“ ist.

Beurteilen Sie, ob ein Kellerautomat anhand des kombinierten Protokolls entscheiden kann, ob der nordafrikanische Standort ruhiger ist. [6 Punkte]

Aufgabenstellung: Aufgabe 4 - Grammatiken und Kellerautomaten · Abitur NRW Informatik LK · Haupttermin 2022

Lösung

Nach den offiziellen Korrekturhinweisen

Erläutern Sie die Produktionen der Grammatik $G_1$ .

Lösung: Aus dem Startsymbol $S$ kann eine Frequenz $F$ und eine mit dem Zeichen $:$ abgetrennte Signalstärke $I$ abgeleitet werden. Darüber hinaus kann das Startsymbol $S$ mit dem Zeichen $;$ ein weiteres Mal angehängt werden, so dass eine beliebig lange Kette von Signaleinträgen entstehen kann. Das Nichtterminal $F$ wird zu einem einzelnen Frequenzeintrag $(ZN.NN$ abgeleitet, vor dem eine öffnende Klammer $($ stehen muss. Das Nichtterminal $I$ wird zu einem $N)$ oder einem $B)$ abgeleitet, die beide Frequenzstärken darstellen können, gefolgt von einer schließenden Klammer $)$ . Das Nichtterminal $N$ wird zu einer Ziffer von $0$ bis $9$ ; das Nichtterminal $Z$ zu einer Ziffer zwischen $1$ bis $9$ , die auch entfallen kann ( $\varepsilon$ -Produktion). Mit Hilfe des Nichtterminals $Z$ kann die erste Stelle eines zweistelligen Frequenzeintrags realisiert werden. Das Nichtterminal $B$ kann in einen Buchstaben zwischen $a$ und $f$ abgeleitet werden. Dieses Nichtterminal ist erforderlich, da Frequenzstärken auch aus Buchstaben bestehen können.

Begründen Sie, warum $G_1$ keine reguläre Grammatik ist.

Lösung: Für eine reguläre Grammatik gilt, dass auf der rechten Seite aller Produktionen entweder ein einzelnes Terminal oder – im Falle einer rechtslinearen Grammatik – ein Terminal gefolgt von einem einzelnen Nichtterminal steht. Auch $\varepsilon$ -Produktionen sind erlaubt. Die Grammatik $G_1$ enthält aber z. B. die Produktion $S \rightarrow F:I$ , die nicht diesen Anforderungen genügt. Die Grammatik ist daher nicht regulär.

Begründen Sie, dass die Sprache der Grammatik $G_1$ regulär ist.

Lösung: Die Sprache zur Grammatik $G_1$ ist regulär. Da nur Signalfrequenzen zwischen $0.00$ und $100.00$ und Signalstärken zwischen $0$ und $f$ vorkommen können, gibt es nur endlich viele Möglichkeiten für einen Signaleintrag. Daher muss es eine reguläre Grammatik geben, die alle möglichen Signaleinträge erzeugt. Diese Signaleinträge werden nun mit dem Zeichen $;$ getrennt aneinandergereiht. Da diese Aneinanderreihung in Einzelschritten aufgebaut werden kann, ist auch das mit einer regulären Grammatik möglich.

Beurteilen Sie, ob ein Kellerautomat anhand des kombinierten Protokolls entscheiden kann, ob der nordafrikanische Standort ruhiger ist.

Lösung: Ein Kellerautomat kann diese Aufgabe lösen, indem er vor dem Auftauchen des Zeichens $!$ für jeden Eintrag $0.00$ ein vorher definiertes Zeichen in den Keller speichert. Sobald das Zeichen $!$ gelesen wird, beginnt der Automat für jedes Auftauchen des Eintrags $0.00$ ein Zeichen aus dem Keller zu entfernen. Ist der Keller leer, ohne dass die Eingabe vollständig abgearbeitet ist, muss überprüft werden, ob die Zeichenfolge $0.00$ noch mindestens einmal vorkommt. Ist das der Fall, ist der Standort in Nordafrika „ruhiger“.

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 - Grammatiken und Grenzen endlicher Aut… · GK · Nachtermin 2022 · Aufgabe 4 - Grammatiken und Kellerautomaten · LK · Nachtermin 2022 ›

Aufgabe 4 - Grammatiken und Kellerautomaten · Abitur NRW Informatik LK · Haupttermin 2022

Aufgabenstellung

Lösung

Mehr Aufgaben zu Grammatiken, Kellerautomaten und Grenzen endlicher Automaten