Zehn Übungen zu Regelformen, Ableitungen und eigenen Entwürfen — vom Zuordnen bis zum Widerlegen.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Ordnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Feste Form oder nicht?
AFB I
In einer regulären Grammatik hat jede Regel die Form A → aB, A → a oder A → ε. Ordnen Sie jede Regel dem passenden Korb zu.
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).
1hat die feste reguläre Form
2hat diese Form nicht
Rechts steht höchstens ein Terminal und danach höchstens ein Nichtterminal. In S → aSb steht S in der Mitte, in A → Bb links, S → AB hat zwei Nichtterminale. A → abB erzeugt zwei Terminale auf einmal — das lässt sich mit einem neuen Nichtterminal zerlegen (A → aX, X → bB), hat aber selbst nicht die feste Form.
Ansatz: Lesen Sie nur die rechte Seite: Wie viele Terminale, wie viele Nichtterminale, in welcher Reihenfolge?
Weiter: Ein Nichtterminal rechts muss das letzte Zeichen sein, und davor steht genau ein Terminal.
A2
Was G ableiten kann
AFB I
Gegeben ist die Grammatik G:
N = {S, A} T = {0, 1} Startsymbol: S Produktionsregeln: S → 0S | 1A A → 0S | 1A | ε
Wenden Sie die Regeln an und entscheiden Sie bei jeder Aussage, ob sie stimmt.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Das Nichtterminal am Ende der Satzform verrät, was zuletzt erzeugt wurde: S nach einer 0 (oder am Anfang), A nach einer 1. Enden darf die Ableitung nur in A — also nur nach einer 1.
Ansatz: Schreiben Sie die Satzformen nacheinander auf, bis nur noch Terminale übrig sind.
Weiter: Welches Nichtterminal darf verschwinden? Danach richtet sich, welche Wörter entstehen.
A3
Die Notation lesen
AFB I
Im Abitur wird eine Grammatik durch Nichtterminale, Terminale, Startsymbol und Produktionsregeln angegeben. Geben Sie zu jedem Teil der Notation seine Bedeutung 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.
Der senkrechte Strich ist nur eine Abkürzung: S → aA | b steht für die beiden Regeln S → aA und S → b. Der Doppelpfeil ⇒ trennt Satzformen einer Ableitung, der einfache Pfeil → steht in Regeln.
Ansatz: Unterscheiden Sie die Pfeile: → gehört zu einer Regel, ⇒ zu einer Ableitung.
Weiter: Großbuchstaben sind Nichtterminale, Kleinbuchstaben und Ziffern Terminale.
A4
Ableitung einer Kommazahl
AFB II
Die Grammatik erzeugt Kommazahlen; d steht für eine Ziffer, k für das Komma:
N = {S, A, B, C} T = {d, k} Startsymbol: S Produktionsregeln: S → dA A → dA | kB | ε B → dC C → dC | ε
Stellen Sie die Ableitung des Worts ddkd dar, indem Sie die Satzformen ordnen.
Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1S
2dA
3ddA
4ddkB
5ddkdC
6ddkd
Jeder Schritt hängt genau ein Zeichen an (oder löscht mit ε das Nichtterminal). Nach dem Komma führt der Weg über B, das genau eine Ziffer verlangt — erst danach darf C mit ε enden. Deshalb ist dd ableitbar, ddk aber nicht.
Ansatz: Die Satzformen werden von Schritt zu Schritt genau ein Zeichen länger — bis auf den letzten Schritt.
Weiter: Nach dem k steht B. Welche Regel hat B?
A5
Mindestens zwei a
AFB II
Mara soll eine reguläre Grammatik für alle Wörter über {a, b} mit mindestens zwei a angeben. Überprüfen Sie ihre Lösung.
In dieser Lösung stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Die ε-Regel gehört zu dem Nichtterminal, dessen Bedeutung die Bedingung erfüllt: B („mindestens zwei a“). Mit B → ε ist die Grammatik korrekt: S ⇒ aA ⇒ abA ⇒ abaB ⇒ aba.
Ansatz: Prüfen Sie jede Bedeutung: Darf das Wort in dieser Situation schon fertig sein?
Weiter: Zwei Zeilen sind falsch — eine davon ist eine Behauptung über reguläre Grammatiken, keine Regel.
A6
Auf jede 1 folgt eine 0
AFB II
Gesucht ist eine reguläre Grammatik für alle Wörter über {0, 1}, in denen auf jede 1 sofort eine 0 folgt, z. B. 0100, 10 oder ε. Stellen Sie die Grammatik auf, indem Sie die Lücken füllen.
Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
S: keine offene 1 · A: 1 erzeugt, die 0 fehlt noch
S → 0 | 1 |
A →
In S darf das Wort enden (S → ε), in A nicht — dort fehlt noch die 0. Nach der 0 ist wieder alles offen, also zurück nach S. Ein Wort wie 0110 scheitert, weil A keine Regel mit 1 hat.
Ansatz: Schreiben Sie zu S und A auf, welches Zeichen jeweils erlaubt ist.
Weiter: A hat genau eine Regel: Es muss eine 0 kommen, danach ist die Lage wie am Anfang.
A7
Reguläre Grammatik möglich?
AFB IIMix
Reguläre Grammatiken beschreiben genau die Sprachen, die auch ein DEA erkennt. Untersuchen Sie, für welche Sprachen es eine reguläre Grammatik gibt.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
aⁿbᵐ: S → aS | bB | ε, B → bB | ε. Höchstens drei b: vier Nichtterminale für 0–3 erzeugte b. Gerade Anzahl Einsen: zwei Nichtterminale. Für aⁿbⁿ, Klammern beliebiger Tiefe und „gleich viele a wie b“ müssten unbeschränkt viele Anzahlen unterschieden werden — dafür gibt es keinen DEA und darum auch keine reguläre Grammatik.
Ansatz: Denken Sie an 9.2.2: Wo müsste man unbeschränkt zählen?
Weiter: Beschränkt zählen (höchstens drei, gerade/ungerade) geht mit endlich vielen Nichtterminalen, der Vergleich zweier beliebig großer Anzahlen nicht.
A8
Wörter der Länge 4
AFB IIITrick
Gegeben ist die Grammatik:
N = {S, A, B} T = {a, b} Startsymbol: S Produktionsregeln: S → aA | bA A → aB | bB B → aS | bS | ε
Bestimmen Sie, wie viele verschiedene Wörter der Länge 4 die Grammatik erzeugt.
Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Jede Ableitung durchläuft S, A, B, S, A, B, … — nach jedem Zeichen wechselt das Nichtterminal. Enden kann sie nur in B, also nach 2, 5, 8, … Zeichen. Wörter der Länge 4 entstehen deshalb gar nicht: 0. Wer 16 zählt, hat nur auf die Zeichen und nicht auf die ε-Regel geschaut.
Ansatz: Verfolgen Sie, welches Nichtterminal nach 1, 2, 3, 4 Zeichen am Ende der Satzform steht.
Weiter: Welche Nichtterminale dürfen verschwinden?
A9
Genau zwei b
AFB III
Entwerfen Sie eine reguläre Grammatik für alle Wörter über {a, b} mit genau zwei b. 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 (je eine Information: 0, 1 oder 2 b erzeugt):Nichtterminale
Anzahl der Regeln, wenn jedes Nichtterminal für jedes erlaubte Zeichen genau eine Regel hat, plus ε-Regeln:Regeln
Anzahl der Wörter der Länge 4 in dieser Sprache:Wörter
Anzahl der Ableitungsschritte ⇒ für ein Wort der Länge 4:Schritte
Grammatik: S → aS | bA, A → aA | bB, B → aB | ε. Ein drittes b hat keine Regel in B — damit ist „genau zwei“ gesichert. Wörter der Länge 4 mit genau zwei b: \(\binom{4}{2}=6\) (aabb, abab, …). Jede Ableitung hat so viele Schritte wie Zeichen und einen Schritt für ε.
Ansatz: Die drei Nichtterminale bedeuten „0 b“, „1 b“, „2 b“. In welchem darf das Wort enden?
Weiter: In B darf kein b mehr kommen — dort gibt es nur B → aB und B → ε.
A10
Nur ein Nichtterminal
AFB III
Tim behauptet: „Die Grammatik mit S → aSb | ε ist regulär, denn sie hat nur ein Nichtterminal.“ Widerlegen Sie die Behauptung, indem Sie die Lücken füllen.
Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.
In S → aSb steht das Nichtterminal ; erlaubt ist es nur . Die Grammatik erzeugt , und diese Sprache erkennt nach 9.2.2 . Gäbe es eine reguläre Grammatik für sie, gäbe es auch einen . Ob eine Grammatik regulär ist, entscheidet also die , nicht die Zahl der Nichtterminale.
Das Gegenargument hat zwei Teile: Die Regel verletzt die feste Form, und keine andere reguläre Grammatik kann dieselbe Sprache erzeugen, weil reguläre Grammatiken und DEA dieselben Sprachen beschreiben. S → aSb ist eine typische kontextfreie Regel (9.3.5).
Ansatz: Wo steht S auf der rechten Seite von S → aSb?
Weiter: Welche Sprache erzeugt S → aSb | ε, und was wissen Sie aus 9.2.2 über sie?
