Automaten und formale Sprachen: Übungen AFB II – Informatik Leistungskurs

Ihr Fortschritt:

0 / 0 Aufgaben

Aufgabenblock — AFB II

Zehn Aufgaben zum Anwenden in neuen Situationen: Sprachen erkennen, Keller und Ableitungen verfolgen, Modelle vergleichen. Erst selbst rechnen, dann prüfen.

Welche Sprache?

AFB II

Gegeben ist der DEA:

Analysieren Sie den Automaten: Beschreiben Sie die Bedeutung der Zustände und geben Sie an, wie viele Wörter der Länge 3 er akzeptiert.

Anzahl = Wörter

Bedeutungen: z1 heißt „zuletzt ein a, aber noch kein aa“, z2 „aa kam schon vor“.

Lösung anzeigen

Der DEA akzeptiert alle Wörter, die das Teilwort aa enthalten. Länge 3: aaa, aab, baa → 3 Wörter

aba wird abgelehnt: Das b dazwischen führt zurück nach z0.

Jedes dritte a

AFB II

Ein Mealy-Automat mit \(\Sigma=\{a,b\}\) und \(\Omega=\{X\}\) hat die Zustände q0 (Start), q1, q2. Mit a geht er von q0 nach q1 und von q1 nach q2 (Ausgabe ε), von q2 zurück nach q0 mit Ausgabe X; b ist überall eine Schleife mit Ausgabe ε. Untersuchen Sie, wie viele X er zur Eingabe aabaaaab ausgibt.

Anzahl X =

Ablaufprotokoll: Zustand, Eingabe, Ausgabe, Folgezustand Schritt für Schritt notieren.

Lösung anzeigen

q0 –a→ q1 –a→ q2 –b→ q2 –a/X→ q0 –a→ q1 –a→ q2 –a/X→ q0 –b→ q0 → XX, also 2

Das Wort enthält sechs a; nach dem dritten und dem sechsten kommt ein X. Die b ändern nichts.

Keller für a²ⁿbⁿ

AFB II

Der Kellerautomat erkennt \(\{a^{2n}b^n\mid n\ge 1\}\); z3 ist Endzustand.

von	Übergang	nach
z0	`(#,a):#`	z1
z0	`(A,a):A`	z1
z1	`(#,a):A#`	z0
z1	`(A,a):AA`	z0
z0	`(A,b):ε`	z2
z2	`(A,b):ε`	z2
z2	`(#,ε):#`	z3

Ermitteln Sie Zustand und Kellerinhalt (oberstes Zeichen links) nach dem Lesen von aaaab.

Zustand =

Keller =

Idee: Nur jedes zweite a legt ein A ab — z0 und z1 unterscheiden „gerade“ und „ungerade“ Anzahl a.

Lösung anzeigen

(z0, #) –a→ (z1, #) –a→ (z0, A#) –a→ (z1, A#) –a→ (z0, AA#) –b→ (z2, A#)

Mit einem weiteren b wird der Keller zu #, der ε-Übergang führt nach z3: aaaabb wird akzeptiert.

Wörter der Länge 4

AFB II

Gegeben ist die kontextfreie Grammatik S → aSb | SS | ε. Belegen Sie mit Ableitungen, welche Wörter der Länge 4 sie erzeugt, und geben Sie deren Anzahl an.

Anzahl = Wörter

Deutung: a wirkt wie „Klammer auf“, b wie „Klammer zu“.

Lösung anzeigen

S ⇒ aSb ⇒ aaSbb ⇒ aabb und S ⇒ SS ⇒ aSbS ⇒ abS ⇒ abaSb ⇒ abab → 2 Wörter

Alle anderen Wörter der Länge 4 sind nicht korrekt „geklammert“, z. B. abba.

Linksableitung

AFB II

Die Grammatik E → T+E | T, T → z | (E) beschreibt Summen. Stellen Sie die Linksableitung von (z)+z dar und geben Sie die Anzahl der Ableitungsschritte an.

Schritte =

Linksableitung: Immer das am weitesten links stehende Nichtterminal ersetzen.

Lösung anzeigen

E ⇒ T+E ⇒ (E)+E ⇒ (T)+E ⇒ (z)+E ⇒ (z)+T ⇒ (z)+z → 6 Schritte

Länge durch 4 teilbar

AFB II

Gesucht ist eine reguläre Grammatik für alle Wörter über {a, b}, deren Länge durch 4 teilbar ist. Bestimmen Sie die Mindestzahl an Nichtterminalen.

Anzahl = Nichtterminale

Entwurf: Jedes Nichtterminal steht für eine Information — hier den Rest der bisherigen Länge bei Division durch 4.

Lösung anzeigen

S (Rest 0), A (Rest 1), B (Rest 2), C (Rest 3) → 4 Nichtterminale

Ist 101 ableitbar?

AFB II

Gegeben ist die reguläre Grammatik S → 0S | 1A, A → 0B | 1S, B → 0A | 1B | ε. Überprüfen Sie, ob das Wort 101 ableitbar ist (ja oder nein).

Antwort:

DEA-Blick: S, A, B sind die Zustände; enden darf die Ableitung nur in B.

Lösung anzeigen

S ⇒ 1A ⇒ 10B ⇒ 101B ⇒ 101 → ja

Die Nichtterminale stehen für den Rest bei Division durch 3 (S: 0, A: 1, B: 2): Die Grammatik erzeugt genau die Binärzahlen mit Rest 2 — 101 ist 5.

Wie viele Zustände?

AFB II

Ein DEA soll genau die Wörter über {a, b} akzeptieren, deren Anzahl an a bei Division durch 5 den Rest 2 lässt. Vergleichen Sie diese Aufgabe mit der Sprache \(\{a^nb^n\}\) und geben Sie die kleinste mögliche Zahl von Zuständen an.

Anzahl = Zustände

Grenzen: Beschränkt zählen geht — hier reichen die fünf möglichen Reste.

Lösung anzeigen

Zustände für die Reste 0 bis 4 → 5 Zustände

Anders als bei \(\{a^nb^n\}\) muss keine unbeschränkte Anzahl gespeichert werden, nur ein Rest — dafür genügen endlich viele Zustände. Ein Fehlerzustand ist nicht nötig.

Ein Zähler statt Keller

AFB II

Die Methode misst die Schachtelungstiefe eines Klammerausdrucks:

Java

public static int tiefe(String s) {
    int t = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            t++;
            if (t > max) max = t;
        } else if (c == ')') {
            t--;
        }
    }
    return max;
}

Werten Sie den Aufruf tiefe("((())())") aus.

Rückgabe =

Tracetabelle: t nach jedem Zeichen notieren; max merkt sich den größten Wert.

Lösung anzeigen

t: 1, 2, 3, 2, 1, 2, 1, 0 → max = 3

t entspricht der Zahl der A im Keller eines Klammer-Kellerautomaten (ohne #).

A10

Kellerhöhe

AFB II

Ein Kellerautomat prüft Klammerausdrücke: Jede „(“ legt ein K ab, jede „)“ entfernt eines; zu Beginn liegt # im Keller. Erklären Sie, warum die Kellerhöhe mit der Schachtelungstiefe zusammenhängt, und geben Sie die größte Anzahl von Zeichen im Keller (einschließlich #) beim Wort (()(())) an.

Höhe = Zeichen

Keller: Die K im Keller sind die noch offenen Klammern.

Lösung anzeigen

Offene Klammern: 1, 2, 1, 2, 3, 2, 1, 0 — maximal 3 K plus # = 4 Zeichen

Jede noch offene Klammer liegt als K im Keller; deshalb ist die Kellerhöhe ohne # genau die aktuelle Schachtelungstiefe.

Übung AFB II

Aufgabenblock — AFB II