Zehn Übungen zum Umwandeln in beide Richtungen — vom Pfeil zur Regel und von der Regel zum Endzustand zE.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Ü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 I
Beim 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 I
Die 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 I
Aus 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 | ε
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.
Aussage 1 von 5
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.
A4
Lauf und Ableitung
AFB II
Der DEA aus A2 liest das Wort 0110. Bestimmen Sie nach jedem Zeichen den Zustand und das Nichtterminal am Ende der Satzform der passenden Ableitung.
Füllen Sie alle Felder aus (Zustände als z0, z1, z2; Nichtterminale als S, A, B; zuletzt ja oder nein) und prüfen Sie dann.
gelesen
Zustand
Nichtterminal am Ende
0
01
011
0110
akzeptiert?
Ableitung: S ⇒ 0S ⇒ 01A ⇒ 011A ⇒ 0110B ⇒ 0110. Das Nichtterminal am Ende ist in jedem Schritt der aktuelle Zustand. Weil z2 Endzustand ist, gibt es B → ε — das Wort wird akzeptiert bzw. erzeugt.
Ansatz: Folgen Sie im Graphen den Pfeilen 0, 1, 1, 0 ab z0.
Weiter: z0 entspricht S, z1 entspricht A, z2 entspricht B.
A5
Ableitung zum DEA-Lauf
AFB II
Mit der Grammatik aus A3 soll das Wort xxy erzeugt werden. Stellen Sie die Ableitung dar, indem Sie die Satzformen ordnen.
Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1S
2xA
3xxA
4xxyB
5xxy
S ⇒ xA ⇒ xxA ⇒ xxyB ⇒ xxy: Der zugehörige DEA-Lauf ist S –x→ A –x→ A –y→ B, und B ist Endzustand.
Ansatz: Die Satzform wächst in jedem Schritt um ein Zeichen.
Weiter: Am Ende verschwindet das Nichtterminal mit einer ε-Regel.
A6
Übergangstabelle erstellen
AFB II
Erstellen Sie zur Grammatik die Übergangstabelle des DEA. Endzustand ist zE (→ Startzustand, doppelt unterstrichen: Endzustand).
Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
Grammatik: S → aA | c, A → bA | cS | a (S wird z0, A wird z1)
Zustand
a
b
c
z0
z1
zE
S → aA ergibt z0 –a→ z1, S → c und A → a führen in den neuen Endzustand zE. A → bA ist eine Schleife, A → cS führt zurück nach z0. Alles andere (b in z0, jedes Zeichen in zE) führt nach zF.
Ansatz: Jede Regel mit Nichtterminal liefert ein Feld; Regeln wie S → c zeigen auf zE.
Weiter: Für Felder ohne passende Regel bleibt nur der Fehlerzustand.
A7
DEA, Grammatik oder beide?
AFB IIMix
Ordnen Sie jede Eigenschaft ein: Gilt sie für DEA, für reguläre Grammatiken oder für beide?
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).
1nur DEA
2nur reguläre Grammatik
3beide
Der DEA erkennt (liest), die Grammatik erzeugt. Weil sich beide ineinander umwandeln lassen, beschreiben sie dieselben Sprachen und haben dieselbe Grenze aus 9.2.2: Endlich viele Zustände bzw. Nichtterminale können nicht unbeschränkt zählen.
Ansatz: Doppelkreis und ε-Regel sind zwei Schreibweisen derselben Idee.
Weiter: Was aus der Umwandelbarkeit folgt, gilt für beide.
A8
Wie viele Regeln?
AFB IIITrick
Der folgende DEA wird in eine reguläre Grammatik umgewandelt; der Fehlerzustand wird dabei weggelassen.
Vollständiger DEA über Σ = {a, b, c}
Ermitteln Sie, wie viele Regeln (einzelne Alternativen) die Grammatik hat.
Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
z0: a und b stehen an einem Pfeil — das sind zwei Regeln (S → aA | bA). z1: drei Zeichen an der Schleife ergeben drei Regeln (A → aA | bA | cA), dazu A → ε. Alles, was nach zF führt oder dort bleibt, fällt weg: 2 + 4 = 6. Wer Pfeile statt Zeichen zählt oder zF mitnimmt, landet bei 3, 4 oder 10.
Ansatz: Zählen Sie Zeichen an den Pfeilen, nicht Pfeile.
Weiter: Endzustände bringen eine zusätzliche Regel mit; zF bringt keine.
A9
Die Regel A → 0
AFB III
Jonas wandelt die Grammatik S → 0A | 1S, A → 1A | 0 in einen DEA um. Beurteilen Sie seine Umwandlung und markieren Sie die fehlerhaften Schritte.
In dieser Lösung stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Eine Regel wie A → 0 beendet die Ableitung. Im DEA wird daraus ein Pfeil in einen eigenen Endzustand zE, von dem jedes weitere Zeichen nach zF führt. So wird genau nach dieser 0 akzeptiert — und nicht mehr danach.
Ansatz: Welche Wörter erzeugt die Grammatik? Enden sie alle mit einer 0 nach A?
Weiter: Prüfen Sie Jonas’ Automaten mit dem Wort 0.
A10
Warum dieselbe Sprache?
AFB III
Zeigen Sie, dass die aus einem DEA konstruierte Grammatik genau die Wörter erzeugt, die der DEA akzeptiert, 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.
Der DEA akzeptiert w = a₁a₂…aₙ genau dann, wenn es einen Lauf z₀ → z₁ → … → zₙ gibt, der in einem endet. Jeder Pfeil dieses Laufs ist eine der Grammatik, also gibt es die Ableitung S ⇒ a₁Z₁ ⇒ … ⇒ a₁…aₙZₙ. Weil zₙ Endzustand ist, gibt es , und die Ableitung endet mit w. Umgekehrt enthält jede Satzform genau ; es gibt den an. Jede Ableitung von w ist deshalb ein des DEA, der in einem Endzustand endet.
Beide Richtungen sind nötig: Jedes akzeptierte Wort ist ableitbar, und jedes ableitbare Wort wird akzeptiert. Der Schlüssel ist, dass die Satzform immer genau ein Nichtterminal ganz rechts hat — es spielt die Rolle des Zustands.
Ansatz: Folgen Sie einem Lauf und schreiben Sie zu jedem Pfeil die zugehörige Regel.
Weiter: Was steht nach k Schritten am Ende der Satzform?
