Aufgaben zu Grammatiken, Kellerautomaten und Grenzen endlicher Automaten

15 Aufgaben zu Grammatiken, Kellerautomaten und Grenzen endlicher Automaten aus dem Abitur NRW Informatik (2021-2023). Mit ausführlicher Lösung.

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · GK · Haupttermin 2023

Teilaufgabe c: Entwerfen einer regulären Grammatik, die alle Spielprotokolle erzeugt, bei denen maximal einmal die weiße Kugel eingelocht wurde, sowie Ableitung der Wörter srswsfsk und swsfsw. Teilaufgabe e: Beurteilung der Behauptung von Jonte, ob ein endlicher Automat überprüfen kann, ob alle 15 roten Kugeln…

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · GK · Haupttermin · Weiterbildungskolleg 2023

Teilaufgabe c: Reguläre Grammatik G entwerfen, die Spielprotokolle mit maximal einmal eingelochter weißer Kugel erzeugt. Durch Ableiten prüfen, ob srswsfsk und swsfsw zur Sprache gehören. Teilaufgabe e: Beurteilen, ob ein endlicher Automat prüfen kann, ob alle 15 roten Kugeln eingelocht wurden.

Aufgabe 4 - Grammatiken und Grenzen endlicher Aut… · GK · Nachtermin 2023

Teilaufgabe d und e: Ableitung des Wortes rbkbrr in Grammatik G, Beschreibung der erlaubten Mischkulturen im Sachzusammenhang, Begründung warum G nicht regulär ist und Entwurf einer regulären Grammatik für L_G. Beurteilung der Entscheidbarkeit der Mischkulturen (1) (kbrb)+ und (2) (k^n b r^n mit n>=2) durch endliche…

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · LK · Haupttermin 2023

Teilaufgaben b, d und e aus Abiturprüfung 2023 Informatik LK NRW (Aufgabe 4): Entwurf einer regulären Grammatik für Spielprotokolle mit höchstens einmaligem Einlochen der weißen Kugel und Ableitung zweier Wörter; Entwurf eines Kellerautomaten zum Vergleich zweier Spielprotokolle hinsichtlich der Häufigkeit von 'w'…

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · LK · Haupttermin · Weiterbildungskolleg 2023

Teilaufgabe b): Entwerfen Sie eine reguläre Grammatik G, die Spielprotokolle mit maximal einmaligem Einlochen der weißen Kugel erzeugt, und entscheiden Sie durch Ableiten, ob srswsfsk und swsfsw dazugehören. Teilaufgabe d): Entwerfen Sie einen Kellerautomaten, der prüft, ob das Zeichen w nach dem Trennzeichen t…

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · LK · Nachtermin 2023

Teilaufgaben d und e: Formale Grammatiken analysieren und entwerfen sowie Grenzen endlicher Automaten und Kellerautomaten beurteilen.

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · GK · Haupttermin 2022

Untersuchung der formalen Grammatik G1 für erweiterte Signalprotokolle (Ableitung des Worts (1.63:c), Bedeutung der Nichtterminale S, F, I, N, Z und Begründung der Nichtregularität) sowie Beurteilung, warum ein endlicher Automat nicht in der Lage ist, zwei durch '!' getrennte Signalprotokolle auf identische Einträge…

Aufgabe 4 - Grammatiken und Grenzen endlicher Aut… · GK · Nachtermin 2022

Teilaufgabe a: Drei aus der Grammatik G_1 ableitbare Wörter ermitteln, zwei gemeinsame Eigenschaften angeben und G_1 so zu G_2 erweitern, dass zusätzlich 'weg' und 'tag' erzeugt werden können. Teilaufgabe e: Begründen, dass es einen endlichen Automaten gibt, der entscheidet, ob ein Wort aus maximal fünf Zeichen…

Aufgabe 4 - Grammatiken und Kellerautomaten · LK · Haupttermin 2022

Teilaufgaben c und e: Erläuterung der Produktionen der Grammatik G1 zur Erzeugung erweiterter Signalprotokolle, Begründung der Nicht-Regularität der Grammatik G1 sowie der Regularität der erzeugten Sprache, und Beurteilung, ob ein Kellerautomat überprüfen kann, ob das Protokoll aus Nordafrika öfter den Eintrag 0.00…

Aufgabe 4 - Grammatiken und Kellerautomaten · LK · Nachtermin 2022

Aufgabe 4 (Teilaufgaben a, c, e): Reguläre Grammatik für Erstlesewörter analysieren und für 'weg' und 'tag' erweitern; nichtdeterministischen Kellerautomaten für Wörter mit maximal doppelt so vielen Konsonanten (b) wie Vokalen (a) entwerfen und die Erkennung von 'babab' darstellen; beurteilen, ob ein endlicher Automat…

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · GK · Haupttermin 2021

Teilaufgaben c und d: Analyse der Grammatik G (Ableitung dreier Wörter unterschiedlicher Länge, Erläuterung im Sachzusammenhang, Begründung für Nicht-Regularität und Entwurf einer regulären Grammatik G') sowie Untersuchung von Schienenovalen (Entscheidung für rrggrrgg und Begründung der Unmöglichkeit eines…

Aufgabe 4 - Grammatiken und Grenzen endlicher Aut… · GK · Haupttermin · Weiterbildungskolleg 2021

Teilaufgabe c: Ermittlung dreier unterschiedlich langer Wörter der Grammatik G, Erläuterung der Bedeutung der Sprache im Sachkontext, Begründung der Nicht-Regularität von G und Entwurf einer regulären Grammatik G'. Teilaufgabe d: Entscheidung, ob das Wort rrggrrgg ein „Oval“ darstellt, sowie Beurteilung der…

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · GK · Nachtermin 2021

Teilaufgabe c) und d): Reguläre Grammatik für den Automaten A entwerfen sowie die Grammatik G_45 bezüglich Wortlängen, Ableitungen der Wörter ggggg und rrbb, Mustereigenschaften der Mosaikzeilen, Nicht-Regularität der Grammatik und Existenz einer regulären Grammatik für dieselbe Sprache untersuchen.

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · LK · Haupttermin 2021

Teilaufgabe c: Gegeben ist die Grammatik G mit Produktionen S -> rrA, A -> gBg, B -> gBg | rr. Zeigen Sie die Ableitung von rrggrrgg und warum rrrr nicht ableitbar ist. Erläutern Sie im Sachzusammenhang die erzeugten Schienenanlagen. Begründen Sie, warum G nicht regulär ist. Entwickeln Sie einen Kellerautomaten für…

Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · LK · Nachtermin 2021

Teilaufgabe c: Ableitungen der Wörter rrbrr, rrggr und rrggrrbrr anhand der Grammatik G ermitteln und die allgemeinen Bildungsregeln der Zeilen erläutern. Teilaufgabe d: Begründen, warum kein endlicher Automat existiert, der Wörter der Form r^n b^m g^(2n) erkennen kann, und einen nichtdeterministischen Kellerautomaten…

Andere Themen: Informatik

Daten und ihre Strukturierung

Algorithmen

Datenbanken

Formale Sprachen und Automaten

Informatiksysteme und Gesellschaft