Grenzen endlicher Automaten: Übungen – Informatik Grundkurs

A1

Mit DEA erkennbar?

AFB I

Ordnen Sie jede Sprache zu: Gibt es einen DEA, der sie erkennt?

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).

1mit DEA erkennbar

2nicht mit DEA erkennbar

Entscheidend ist, ob unbeschränkt gezählt oder gespeichert werden muss. aⁿbᵐ sieht aus wie aⁿbⁿ, verlangt aber keine gleiche Anzahl — ein DEA merkt sich nur, ob schon ein b kam. „Durch 4 teilbar“ braucht nur die Reste 0 bis 3; {aⁿbⁿ | n ≤ 4} ist endlich. Typischer Fehler: jede Sprache mit „Anzahl“ im Namen für nicht erkennbar halten.

Ansatz: Fragen Sie bei jeder Sprache: Muss sich der Automat eine Zahl ohne obere Grenze merken?

Weiter: Endliche Sprachen und Zählen „modulo“ oder „bis zu einer festen Grenze“ schafft ein DEA.

A2

Stimmt das? — Grenzen

AFB I

Nennen Sie zu jeder Aussage über die Grenzen endlicher Automaten, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.

Aussage 1 von 5

Zwei Verwechslungen stecken in den falschen Aussagen: „endlich viele Zustände“ heißt nicht „endlich viele akzeptierte Wörter“, und „unendliche Sprache“ heißt nicht „nicht regulär“. Begrenzt ist nur, wie viele Vorgeschichten ein DEA auseinanderhalten kann.

Ansatz: Unterscheiden Sie: Wie viele Wörter akzeptiert ein DEA — und wie viele Vorgeschichten kann er unterscheiden?

Weiter: Denken Sie an a*: ein Zustand, unendlich viele Wörter.

A3

Schubfach zählen

AFB I

Ein DEA hat 12 Zustände. Er liest nacheinander die Wörter a⁰ = ε, a¹, a², … . Bestimmen Sie, wie viele dieser Wörter man mindestens betrachten muss, damit sicher zwei davon im selben Zustand enden.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.

Mit 12 Wörtern könnte jedes seinen eigenen Zustand haben. Erst das 13. Wort erzwingt eine Wiederholung (Schubfachprinzip: k + 1 Objekte, k Fächer). Häufigster Fehler: 12 — oder a⁰ = ε nicht mitzuzählen und a¹ bis a¹² zu betrachten. Das sind aber nur 12 Wörter.

Ansatz: Schubfachprinzip: Wie viele Gegenstände braucht man für k Fächer, damit ein Fach doppelt belegt ist?

Weiter: a⁰ bis a¹² — zählen Sie genau, wie viele Wörter das sind.

A4

Begriffe des Beweises

AFB I

Geben Sie zu jedem Begriff die passende Beschreibung an, indem Sie beide verbinden.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.

„Gleicher Zustand“ ist der Dreh- und Angelpunkt: Er bedeutet nicht „gleiches Wort“, sondern „ab hier nicht mehr unterscheidbar“. Deshalb reicht es im Beweis, eine Fortsetzung zu finden, die für die eine Vorgeschichte ins Ziel führt und für die andere nicht.

Ansatz: Beginnen Sie mit den Begriffen, die Sie sicher kennen, z. B. „reguläre Sprache“.

Weiter: Eine endliche Sprache kann man Wort für Wort als Pfad in einen DEA einbauen.

A5

Beweis: Palindrome

AFB II

Mit derselben Idee wie bei L = {aⁿbⁿ | n ≥ 0} lässt sich zeigen, dass kein DEA die Palindrome über {a, b} erkennt (Palindrome lesen sich vorwärts und rückwärts gleich). Ordnen Sie die Beweisschritte in die richtige Reihenfolge ein.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.

1Annahme: Ein DEA A mit k Zuständen erkennt die Palindrome über {a, b}.

2Betrachte die k + 1 Vorgeschichten b, ab, aab, …, aᵏb.

3Schubfach: Zwei davon, aⁱb und aʲb mit i < j, enden im selben Zustand.

4Hängt man an beide aⁱ an, behandelt A die Wörter aⁱbaⁱ und aʲbaⁱ gleich.

5aⁱbaⁱ ist ein Palindrom, aʲbaⁱ wegen i ≠ j nicht.

6Widerspruch — kein DEA erkennt die Palindrome.

Hier sind die Vorgeschichten nicht aⁱ, sondern aⁱb: Das b markiert die Mitte, sodass nach dem Anhängen von aⁱ genau eines der Wörter symmetrisch ist. Häufigster Fehler: den Widerspruch vor dem Vergleich einordnen. Erst der Vergleich „eines in L, eines nicht“ macht die gleiche Behandlung zum Widerspruch.

Ansatz: Ein Widerspruchsbeweis beginnt mit der Annahme und endet mit dem Widerspruch.

Weiter: Dazwischen: Vorgeschichten → Schubfach → gleiche Fortsetzung anhängen → Wörter vergleichen.

A6

Beschränkt geht — aber teuer

AFB II

Für eine feste Obergrenze m ist L_m = {aⁿbⁿ | 0 ≤ n ≤ m} endlich und damit regulär. Ermitteln Sie, wie viele Zustände ein vollständiger DEA für L_m mindestens braucht — einschließlich des Fehlerzustands zF.

Tragen Sie die Mindestzahl der Zustände ein und prüfen Sie dann. Enter prüft ebenfalls.

Obergrenze m	1	2	3	10
Zustände (mit zF)

Der DEA braucht z0 (Start, akzeptiert ε), je einen Zustand für a¹ … aᵐ, dann Zustände „noch r b nötig“ für r = m − 1 … 1, einen Endzustand „fertig“ und zF: 1 + m + (m − 1) + 1 + 1 = 2m + 2. Für m = 10 also 22. Typischer Fehler: zF vergessen (21) oder für jedes Wort einen eigenen Pfad bauen. Mit wachsendem m wächst die Zahl ohne Grenze — genau deshalb gibt es für unbeschränktes n keinen DEA.

Ansatz: Zeichnen Sie den DEA für m = 1: Er akzeptiert nur ε und ab. Vergessen Sie zF nicht.

Weiter: Nach dem ersten b muss der Automat noch wissen, wie viele b fehlen. Suchen Sie für m = 1, 2, 3 ein Muster.

A7

Schubfach an einem Beispiel

AFB II

Ein DEA A mit 5 Zuständen soll L₌ = {w ∈ {a, b}* | w enthält gleich viele a wie b} erkennen. Wenden Sie die Beweisidee Schritt für Schritt auf diesen Fall an (Wörter ohne Leerzeichen, Antwort in Schritt 4: angenommen oder abgelehnt).

Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.

Anzahl der Vorgeschichten a⁰, a¹, …, a⁵
Mindestens so viele davon enden sicher im selben Zustand
Angenommen, a² und a⁵ enden im selben Zustand. Kürzester Anhang w mit a²w ∈ L₌
Wenn A das Wort a²bb richtig behandelt: Was macht A mit a⁵bb?

Sechs Vorgeschichten, fünf Zustände — zwei teilen sich sicher einen Zustand. Da a²bb ∈ L₌ angenommen wird, muss A auch a⁵bb annehmen, obwohl dort 5 a auf 2 b kommen. Typischer Fehler im letzten Schritt: „abgelehnt“ antworten, weil a⁵bb nicht zu L₌ gehört. Gefragt ist aber, was A tut — und genau darin liegt der Widerspruch.

Ansatz: k Zustände, k + 1 Vorgeschichten: Das Schubfachprinzip erzwingt eine Wiederholung.

Weiter: Gleicher Zustand ⇒ gleiche Entscheidung für jede gleiche Fortsetzung — unabhängig davon, was richtig wäre.

A8

Leonies Automat

AFB II Mix

Leonie behauptet, ihr DEA erkenne L = {aⁿbⁿ | n ≥ 0}. Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.

Leonies DEA (Σ = {a, b})

Analysieren Sie den Automaten wie in 8.1.3 und markieren Sie alle zutreffenden Aussagen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.

A0/A1 merken sich im a-Block, ob die Länge bisher gerade oder ungerade ist, B0/B1 dasselbe im b-Block. Akzeptiert werden alle Wörter aⁿbᵐ mit gerader Gesamtlänge. Darunter sind alle aⁿbⁿ, aber auch aaab. Typischer Fehler: aus „akzeptiert alle Wörter aus L“ zu schließen, dass der Automat L erkennt — er darf auch nur Wörter aus L akzeptieren. Kein zusätzlicher Zustand hilft: L ist nicht regulär.

Ansatz: Testen Sie systematisch: ε, ab, aabb, aaab, abab. Welche Bedeutung haben A0 und A1?

Weiter: „Erkennen“ heißt: genau die Wörter aus L akzeptieren — nicht mehr und nicht weniger.

A9

Fehlersuche: ein Beweis

AFB III

Tim hat bewiesen, dass kein DEA L = {aⁿbⁿ | n ≥ 0} erkennt. Überprüfen Sie seinen Beweis — drei Zeilen sind fehlerhaft.

In diesem Beweis stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.

Zeile 4 sieht verdächtig aus, ist aber korrekt: Statt bⁱ darf man auch bʲ anhängen — dann liegt aʲbʲ in L und aⁱbʲ nicht. Die echten Fehler: In Zeile 2 fehlt a⁰, dadurch sind es nur k Wörter und das Schubfachprinzip greift nicht. Zeile 7 zieht einen zu schwachen Schluss, Zeile 8 nennt einen falschen Grund.

Ansatz: Zählen Sie in Zeile 2 genau, wie viele Vorgeschichten es sind.

Weiter: Prüfen Sie die Schlusszeilen: Hängt das Argument von einem bestimmten k ab? Ist a* regulär?

A10

Zählen, das keins ist

AFB III Trick

Gegeben ist L = {w ∈ {a, b}* | das Teilwort ab kommt in w genauso oft vor wie ba}. Auf den ersten Blick sieht das nach unbeschränktem Zählen aus. Beurteilen Sie die Sprache, indem Sie die Menüs ausfüllen.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

aabaa gehört zu L:

abab gehört zu L:

babb gehört zu L:

Kurzbeschreibung von L:

Urteil:

Die Falle: „genauso oft wie“ klingt nach aⁿbⁿ. Aber ab (Wechsel a→b) und ba (Wechsel b→a) müssen sich immer abwechseln. Ihre Anzahlen unterscheiden sich deshalb höchstens um 1, und gleich sind sie genau dann, wenn das Wort mit demselben Zeichen beginnt und endet. Ein DEA merkt sich nur erstes und letztes Zeichen: Start, „a…a“, „a…b“, „b…b“, „b…a“ — fünf Zustände, kein Fehlerzustand.

Ansatz: Zählen Sie in aabaa und abab die Teilwörter ab und ba. Was fällt auf?

Weiter: Zwischen zwei ab muss immer ein ba liegen. Wovon hängt es also ab, ob beide Anzahlen gleich sind?

Übungen: Grenzen eines DEA

Übungsaufgaben