Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Ü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 IIn 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 IGegeben ist die Grammatik G:
N = {S, A}
T = {0, 1}
Startsymbol: S
Produktionsregeln:
S → 0S | 1A
A → 0S | 1A | ε
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.
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 IIm 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.