Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Nachverfolgen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Natürlich oder formal?
AFB IOrdnen Sie jede Sprache 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).
1natürliche Sprache
2formale Sprache
Natürliche Sprachen sind gewachsen — auch Latein und Gebärdensprachen, obwohl man sie lernen muss. Formale Sprachen sind künstlich festgelegt: Bei Java, SQL, hh:mm oder IBAN entscheiden exakte Regeln, ob eine Zeichenfolge dazugehört. Typischer Fehler: „schwer zu lernen“ mit „formal“ gleichsetzen.
Ansatz: Ist die Sprache historisch entstanden oder wurde sie für einen Zweck festgelegt?
Weiter: Bei formalen Sprachen gibt es exakte Regeln, die jedes Wort eindeutig einordnen.
A2
Stimmt das? — Grundbegriffe
AFB INennen Sie zu jeder Aussage, ob sie stimmt.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
ε ist der häufigste Stolperstein: Es ist ein Wort, kein Zeichen — und eine Sprache, die nur ε enthält, ist nicht leer.
Ansatz: Unterscheiden Sie Zeichen, Wort und Sprache.
Weiter: Eine Menge mit einem Element ist nicht leer — auch wenn das Element „leer“ heißt.
A3
Begriffe am Beispiel
AFB IÜber dem Alphabet {0, 1, 2} ist 2012 ein Wort. Geben Sie zu jedem Begriff ein passendes Beispiel 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.
Das Alphabet ist die Zeichenmenge, eine Sprache eine Menge von Wörtern. Präfix und Suffix sind Anfangs- und Endstück:
20 steht vorn, 12 hinten. Typischer Fehler: Alphabet und Sprache verwechseln — beide sind Mengen, aber von Zeichen bzw. von Wörtern.Ansatz: Welche Einträge sind Mengen, welche einzelne Wörter?
Weiter: Das Präfix steht am Anfang des Worts, das Suffix am Ende.
A4
Wörter zählen
AFB IIEs ist \(\Sigma=\{0,1,2\}\). Berechnen Sie die Anzahlen Schritt für Schritt.
Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
- Anzahl der Wörter der Länge 1
- Anzahl der Wörter der Länge 2
- Anzahl der Wörter der Länge 4
- Anzahl der Wörter mit höchstens 2 Zeichen (ε mitzählen)
\(|\Sigma^n|=3^n\): 3, 9, 81. Für „höchstens 2 Zeichen“ werden die Längen 0, 1 und 2 addiert: 1 + 3 + 9 = 13. Typischer Fehler: ε vergessen (12) oder \(3\cdot 4=12\) statt \(3^4\) rechnen.
Ansatz: Für jede Stelle gibt es 3 Möglichkeiten.
Weiter: Länge 0 hat genau ein Wort: ε.
A5
Das Wort vermessen
AFB IIÜber dem Alphabet der Kleinbuchstaben ist w = informatik. Ermitteln Sie die gesuchten Werte.
Tragen Sie die Werte ein und prüfen Sie dann. Enter prüft ebenfalls.
| Größe | Wert |
|---|---|
| |w| | |
| |w|i | |
| Anzahl der Präfixe (mit ε und w) | |
| Anzahl der Teilwort-Positionen der Länge 3 |
Ein Wort der Länge n hat n + 1 Präfixe: ε, i, in, …, informatik. Ein Teilwort der Länge 3 kann an den Positionen 1 bis 8 beginnen (n − 3 + 1 = 8). Typischer Fehler: bei den Präfixen ε oder das ganze Wort nicht mitzuzählen (9 oder 10).
Ansatz: Zählen Sie die Buchstaben einzeln ab.
Weiter: Ein Präfix endet nach 0, 1, …, n Zeichen. Wo kann ein Teilwort der Länge 3 frühestens und spätestens beginnen?
A6
Sprachen nach Größe
AFB IIEs ist Σ = {0, 1, 2}. Ordnen Sie die Sprachen nach der Anzahl ihrer Wörter ein — von wenigen zu vielen.
Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1∅
2{ε}
3Σ¹ (alle Wörter der Länge 1)
4{w ∈ Σ* | |w| ≤ 1}
5Σ² (alle Wörter der Länge 2)
6Σ³ (alle Wörter der Länge 3)
7Σ* (alle Wörter)
Anzahlen: 0, 1, 3, 4, 9, 27, unendlich. {w | |w| ≤ 1} enthält ε und die drei Wörter der Länge 1. Typischer Fehler: ∅ und {ε} gleichsetzen — die leere Sprache hat 0 Wörter, {ε} genau eines.
Ansatz: Bestimmen Sie für jede Sprache die Anzahl der Wörter.
Weiter: Σ* enthält Wörter jeder Länge — wie viele sind das?
A7
Die Sprache eines DEA
AFB II MixEin DEA über Σ = {0, 1} akzeptiert genau die Wörter, die auf 0 enden. Seine Sprache heißt L. Untersuchen Sie L und markieren Sie alle zutreffenden Aussagen.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.
Jede Sprache eines DEA über {0, 1} ist eine Teilmenge von {0, 1}*. ε endet auf gar nichts, gehört also nicht dazu.
0110 enthält zweimal die 1. Für „endet auf 0“ reicht ein DEA mit zwei Zuständen (9.1) — ein Keller ist unnötig.Ansatz: Setzen Sie kurze Wörter ein: ε, 0, 10, 0110.
Weiter: Ein DEA merkt sich hier nur das zuletzt gelesene Zeichen.
A8
Fehlersuche: Jonas’ Notizen
AFB IIIJonas hat Notizen zu Σ = {a, b, c} geschrieben. Überprüfen Sie sie — drei Zeilen sind fehlerhaft.
In dieser Lösung stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Zeile 4 wirkt seltsam, stimmt aber: Das leere Präfix steht vor jedem Wort. Die Fehler betreffen die Länge (Zeichen zählen, nicht Sorten), die Endlichkeit jedes einzelnen Worts und den Begriff Teilmenge.
Ansatz: Prüfen Sie jede Zeile gegen die Definitionen aus der Stichliste.
Weiter: Unendlich viele Wörter heißt nicht: unendlich lange Wörter.
A9
Syntax oder Semantik?
AFB IIILegen Sie für jedes Beispiel fest, welche Art von Fehler vorliegt.
Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
int n = 3 * ; in Java:
int[] a = new int[3]; a[3] = 1; in Java:
String s = "5" + 5; in Java:
Datum 31.04.2027 im Format TT.MM.JJJJ:
„Der Tisch trinkt die Farbe.“ im Deutschen:
Nur
3 * ; verletzt den Aufbau. Der Index 3 ist in einem Feld der Länge 3 korrekt geschrieben, aber ungültig (Laufzeitfehler). "5" + 5 ist erlaubt und ergibt den Text 55. Der 31. April hat die Form TT.MM.JJJJ, existiert aber nicht; der Satz ist grammatisch korrekt, aber sinnlos.Ansatz: Fragen Sie zuerst: Ist die Form korrekt? Erst dann: Stimmt die Bedeutung?
Weiter: Syntax = Aufbau, Semantik = Bedeutung. Ein Laufzeitfehler entsteht bei korrekt gebildetem Code.
A10
Die leere Sprache?
AFB III TrickTim behauptet: „Die Sprache {ε} ist leer — sie enthält 0 Wörter.“ Widerlegen Sie die Behauptung, indem Sie die richtige Anzahl der Wörter in {ε} angeben.
Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Die Falle: ε sieht nach „nichts“ aus. {ε} enthält aber genau ein Wort — das leere Wort. Leer ist nur ∅. Der Unterschied ist wichtig: Ein Automat, der nur ε akzeptiert, akzeptiert etwas; einer für ∅ akzeptiert gar nichts.
Ansatz: Wie viele Elemente stehen zwischen den Mengenklammern?
Weiter: ε ist ein Wort — das Wort der Länge 0.