Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zum Zuordnen, Ablesen, Umwandeln und Begründen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Was wird woraus?
AFB IBeim Umwandeln eines DEA in eine reguläre Grammatik entspricht jedem Teil des Automaten ein Teil der Grammatik. Ordnen Sie die Teile einander zu.
Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Zustände werden Nichtterminale, Pfeile werden Regeln, Endzustände bekommen eine ε-Regel. Der Fehlerzustand entfällt: Aus ihm kann nie ein Wort entstehen, also braucht man auch keine Regeln dafür.
Ansatz: Ein Pfeil hat einen Start, ein Zeichen und ein Ziel — genau wie die Regel A → aB.
Weiter: Welcher Teil der Grammatik markiert Stellen, an denen ein Wort fertig sein darf?
A2
Regeln aus dem Graphen
AFB IDie Zustände z0, z1, z2 werden zu den Nichtterminalen S, A, B.
DEA über Σ = {0, 1}
Geben Sie alle Regeln an, die zur Grammatik dieses DEA gehören.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Jeder der sechs Pfeile ergibt eine Regel: S → 0S | 1A, A → 1A | 0B, B → 1A | 0S; dazu B → ε, weil nur z2 Endzustand ist. Die Grammatik erzeugt die Wörter, die auf
10 enden.Ansatz: Gehen Sie Pfeil für Pfeil vor: Start = linke Seite, Zeichen und Ziel = rechte Seite.
Weiter: ε-Regeln gibt es nur bei Endzuständen — hier nur bei z2.
A3
Den DEA ablesen
AFB IAus der folgenden Grammatik wird ein DEA konstruiert (S wird zum Startzustand):
N = {S, A, B}
T = {x, y}
Startsymbol: S
Produktionsregeln:
S → xA | yS
A → xA | yB
B → xS | yB | ε
T = {x, y}
Startsymbol: S
Produktionsregeln:
S → xA | yS
A → xA | yB
B → xS | yB | ε
Entnehmen Sie der Grammatik, ob die Aussagen über den DEA stimmen.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Die Grammatik ist deterministisch und vollständig: je Nichtterminal und Zeichen genau eine Regel. Deshalb entsteht ein DEA ohne Fehlerzustand und ohne zusätzlichen Endzustand.
Ansatz: Zählen Sie je Nichtterminal die Regeln mit x und mit y.
Weiter: zE braucht man nur bei Regeln, die mit einem Terminal enden.