Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Ü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?