Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Zuordnen, Ableiten, Nachverfolgen und Beurteilen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Welcher Grammatiktyp?
AFB IOrdnen Sie jede Grammatik nach der Form ihrer Regeln dem passenden Korb zu (S ist jeweils Startsymbol).
Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1regulär
2kontextfrei, nicht regulär
3nicht kontextfrei
Regulär: nur A → aB, A → a, A → ε. Kontextfrei: links genau ein Nichtterminal, rechts beliebig — dazu gehören Nichtterminale in der Mitte (aSc, (S)) oder mehrere (SS, AB). Stehen links mehrere Symbole (cB → Bc, aS → Sa), hängt die Ersetzung vom Kontext ab: nicht kontextfrei.
Ansatz: Schauen Sie zuerst auf die linken Seiten: Steht dort immer genau ein Nichtterminal?
Weiter: Dann die rechten Seiten: Hat jede die feste reguläre Form?
A2
Was S → xSy | z erzeugt
AFB IGegeben ist die Grammatik G mit N = {S}, T = {x, y, z}, Startsymbol S und S → xSy | z. Wenden Sie die Regeln an und entscheiden Sie.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
L(G) = {xⁿzyⁿ | n ≥ 0}: links und rechts vom z gleich viele x und y. Das z markiert die Mitte — ein Kellerautomat weiß daran, wann er vom Ablegen zum Entnehmen wechseln muss.
Ansatz: Schreiben Sie die Ableitungen hin, statt zu raten.
Weiter: Jede Anwendung von S → xSy fügt links ein x und rechts ein y ein.
A3
Grammatik und Sprache
AFB IGeben Sie zu jeder Grammatik (Startsymbol S) die erzeugte Sprache an.
Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
S → aSa | a legt bei jedem Schritt zwei a an, am Ende eins: 1, 3, 5, … Zeichen. S → aSbS | ε ist die Klammergrammatik mit a statt ( und b statt ) — erzeugt z. B. aabbab. S → aS | ε ist sogar regulär.
Ansatz: Leiten Sie zu jeder Grammatik die kürzesten zwei, drei Wörter ab.
Weiter: Achten Sie darauf, welche Regel die Ableitung beendet: ε, b, a oder ab?
A4
Linksableitung eines Ausdrucks
AFB IIDie Grammatik beschreibt Summen, z steht für eine Zahl:
N = {A, T}
T = {z, +, (, )}
Startsymbol: A
Produktionsregeln:
A → T+A | T
T → (A) | z
T = {z, +, (, )}
Startsymbol: A
Produktionsregeln:
A → T+A | T
T → (A) | z
Stellen Sie die Linksableitung von z+(z) dar, indem Sie die Satzformen ordnen.
Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1A
2T+A
3z+A
4z+T
5z+(A)
6z+(T)
7z+(z)
Linksableitung: Immer das am weitesten links stehende Nichtterminal ersetzen. Deshalb wird das T vor dem + zuerst zu z, erst danach das A dahinter.
Ansatz: Welches Nichtterminal steht in T+A am weitesten links?
Weiter: Die Klammer entsteht aus T → (A).
A5
Kellerinhalte verfolgen
AFB IIDer Kellerautomat erkennt {aⁿbcⁿ | n ≥ 0}. Der Keller wird von oben nach unten notiert, das oberste Zeichen steht links.
Kellerautomat: Eingabealphabet Σ = {a, b, c}, Kelleralphabet Γ = {A, #}
Fehlt ein passender Übergang, wird die Eingabe abgelehnt.
Bestimmen Sie Zustand und Kellerinhalt nach jedem Zeichen von aabcc.
Füllen Sie alle Felder aus (Zustände als z0, z1, z2; Keller wie A# mit dem obersten Zeichen links) und prüfen Sie dann.
| gelesen | Zustand | Keller (oben links) |
|---|---|---|
a | ||
aa | ||
aab | ||
aabc | ||
aabcc |
Jedes a legt ein A ab, b ändert den Keller nicht (es wird A entnommen und wieder abgelegt), jedes c entnimmt ein A. Nach
aabcc liegt nur noch # oben — der ε-Übergang (#,ε):# führt nach z2: akzeptiert.Ansatz: (#,a):A# heißt: # wird entnommen, dann werden A und # abgelegt — A liegt oben.
Weiter: Beim b wird das oberste Zeichen entnommen und unverändert wieder abgelegt.
A6
Palindrome gerader Länge
AFB IILena hat eine Grammatik für alle Palindrome gerader Länge über {a, b} notiert und kommentiert. Überprüfen Sie ihre Aussagen.
In dieser Lösung stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Die Sprache ist kontextfrei und nicht regulär — aber das zweite folgt nicht aus der Form einer einzelnen Grammatik. Ein Nachweis braucht ein Argument über alle möglichen DEA bzw. Grammatiken. (Der Kellerautomat zu dieser Sprache muss die Mitte raten und ist nichtdeterministisch.)
Ansatz: Prüfen Sie die Beispiele mit einer eigenen Ableitung.
Weiter: Unterscheiden Sie: Eigenschaft einer Grammatik — Eigenschaft einer Sprache.
A7
Modelle im Vergleich
AFB II MixVergleichen Sie DEA, Mealy-Automat, Kellerautomat und Grammatiken: Welche Aussagen stimmen?
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Reguläre Grammatiken sind spezielle kontextfreie Grammatiken, und ein DEA ist ein Kellerautomat mit unbenutztem Keller. Ein Mealy-Automat hat trotz Ausgabe nur endlich viele Zustände — er zählt nicht weiter als ein DEA. {aⁿbⁿcⁿ} überfordert auch den Keller: Nach dem Vergleich von a und b ist die Anzahl verbraucht.
Ansatz: Ordnen Sie die Modelle nach ihrem Gedächtnis: Zustand — Zustand mit Ausgabe — Zustand und Keller.
Weiter: Für {aⁿbⁿcⁿ} müsste man eine Anzahl zweimal vergleichen.
A8
Wie viele Bäume?
AFB III TrickGegeben ist die Grammatik mit S → SS | ab. Ermitteln Sie, wie viele verschiedene Ableitungsbäume es für das Wort ababab gibt.
Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Die Wurzel wird mit S → SS in zwei Teile zerlegt: ab | abab oder abab | ab. Der Teil abab braucht wieder S → SS, der Rest S → ab — jeweils genau eine Möglichkeit. Also 2 Bäume: Die Grammatik ist mehrdeutig. Wer 1 sagt, hat nur eine Linksableitung notiert; wer 3 sagt, zählt die Stellen zwischen den ab.
Ansatz: Welche Aufteilungen des Worts in zwei nichtleere Teile aus ab-Blöcken erlaubt S → SS an der Wurzel?
Weiter: Ein Teil aus genau einem ab hat nur einen Baum.
A9
a, b, c, d geschachtelt
AFB IIIEntwerfen Sie eine kontextfreie Grammatik für L = {aⁿbᵐcᵐdⁿ | n, m ≥ 0} und halten Sie Ihren Entwurf in Zahlen fest.
Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
- Mindestzahl der Nichtterminale (eines für den äußeren a…d-Teil, eines für den inneren b…c-Teil): Nichtterminale
- Anzahl der Regeln (Alternativen) Ihrer Grammatik: Regeln
-
Anzahl der Ableitungsschritte ⇒ für
aabcdd: Schritte - Anzahl der Wörter der Länge 4 in L: Wörter
Grammatik: S → aSd | T, T → bTc | ε. Ableitung: S ⇒ aSd ⇒ aaSdd ⇒ aaTdd ⇒ aabTcdd ⇒ aabcdd (5 Schritte). Länge 4 heißt n + m = 2:
aadd, abcd, bbcc.Ansatz: Von außen nach innen: Erst die a…d-Paare erzeugen, dann in den b…c-Teil wechseln.
Weiter: S → aSd | T und T → bTc | ε.
A10
Welches Modell genügt?
AFB IIIBeurteilen Sie für jede Sprache, welches Modell mindestens nötig ist.
Wählen Sie für jede Zeile eine Stufe: 1 = DEA genügt, 2 = Kellerautomat nötig, 3 = auch Kellerautomat reicht nicht. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = DEA genügt3 = mehr als ein Kellerautomat
Binärzahlen, deren Wert durch 5 teilbar ist
{aⁿbⁿ⁺¹ | n ≥ 0}
korrekt geschachtelte if-else-Blöcke beliebiger Tiefe
{aⁿbⁿcⁿ | n ≥ 0}
Wörter über {a, b} mit höchstens 100 Zeichen
Palindrome über {a, b}
Teilbarkeit durch 5 braucht nur den Rest (5 Zustände); endliche Sprachen sind immer regulär. Paarweise Abhängigkeiten wie aⁿbⁿ⁺¹, Schachtelung und Spiegelung passen zum Keller. Bei aⁿbⁿcⁿ sind zwei Vergleiche nötig — das geht mit einem Keller nicht (nicht kontextfrei).
Ansatz: Fragen Sie: Muss man unbeschränkt zählen? Wenn ja: einmal oder mehrfach vergleichen?
Weiter: Endliche Sprachen und Reste bei Division brauchen nur endlich viele Zustände.