Aufgabenblock — AFB I
Zehn Standardaufgaben zum Reproduzieren: Graphen und Tabellen lesen, Keller verfolgen, Regeln anwenden. Bei jeder Aufgabe gibt es eine Erinnerung und die Lösung zum Aufklappen.
Ein vollständiger DEA hat die Zustände z0, z1, z2 und den Fehlerzustand zF sowie das Eingabealphabet \(\Sigma=\{a,\,b,\,c,\,d\}\). Berechnen Sie, wie viele Übergänge (Pfeile einschließlich Schleifen) sein Zustandsgraph hat.
Lösung anzeigen
\(|Z|\cdot|\Sigma| = 4\cdot 4\) = 16 Übergänge
Die vier Schleifen an zF zählen mit.
Der DEA zählt die Einsen eines Binärworts:
Entnehmen Sie dem Graphen, in welchem Zustand der DEA nach 1101011 steht.
Lösung anzeigen
z0 → z1 → z2 → z2 → z0 → z0 → z1 → z2 → z2
Das Wort enthält fünf Einsen; 5 : 3 hat den Rest 2. Es wird abgelehnt, denn nur z0 ist Endzustand.
Ein Mealy-Automat mit \(\Sigma=\{a,b\}\) und \(\Omega=\{0,1\}\) ist durch die Tabelle gegeben (Folgezustand / Ausgabe):
| Zustand | a | b |
|---|---|---|
| z0 | z1 / 0 | z0 / ε |
| z1 | z0 / 1 | z1 / ε |
Geben Sie das Ausgabewort zur Eingabe abaab an (ohne Leerzeichen).
Lösung anzeigen
z0 –a/0→ z1 –b/ε→ z1 –a/1→ z0 –a/0→ z1 –b/ε→ z1 → 010
Die beiden b geben nichts aus.
Ein Kellerautomat für \(\{a^nb^n\mid n\ge 0\}\) mit Vorbelegungszeichen # hat die Übergänge:
| von | Übergang | nach |
|---|---|---|
| z0 | (#,a):A# | z1 |
| z1 | (A,a):AA | z1 |
| z1 | (A,b):ε | z2 |
| z2 | (A,b):ε | z2 |
| z2 | (#,ε):# | z3 |
Bestimmen Sie, wie viele Zeichen (einschließlich #) nach dem Lesen von aaab im Keller liegen.
Lösung anzeigen
# → A# → AA# → AAA# → AA# → 3 Zeichen
Drei a legen drei A ab, das b entfernt eines.
Gegeben ist die Grammatik mit N = {S}, T = {a, b, c}, Startsymbol S und S → aSc | b. Wenden Sie die Regel S → aSc dreimal und danach S → b an. Geben Sie das entstehende Wort an.
Lösung anzeigen
S ⇒ aSc ⇒ aaScc ⇒ aaaSccc ⇒ aaabccc
In der Anlage des Abiturs steht die Grammatik
T = {1, 2, a, c}
Startsymbol: S
Produktionsregeln:
S → 1A | 2B
A → 1B
B → aS | cS | a | c
Ermitteln Sie, wie viele einzelne Produktionsregeln sie enthält.
Lösung anzeigen
2 + 1 + 4 = 7 Regeln
Die Grammatik ist regulär: jede Regel hat die Form X → aY oder X → a.
Aus der regulären Grammatik S → aA | b, A → bS | a soll ein DEA entstehen. Ordnen Sie jedem Nichtterminal einen Zustand zu und geben Sie an, wie viele Zustände der DEA ohne Fehlerzustand hat.
Lösung anzeigen
S, A und zE → 3 Zustände
zE ist Endzustand; S → b und A → a führen dorthin.
Erstellen Sie aus dem DEA aus A2 die zugehörige reguläre Grammatik und geben Sie an, wie viele Regeln (einzelne Alternativen) sie hat.
Lösung anzeigen
3 Zustände · 2 Zeichen = 6 Pfeil-Regeln, dazu S → ε für den Endzustand z0 = 7 Regeln
S → 0S | 1A | ε, A → 0A | 1B, B → 0B | 1S.
Stellen Sie alle Wörter der Länge höchstens 3 über \(\Sigma=\{a,b\}\) geordnet nach der Länge dar — das leere Wort eingeschlossen — und geben Sie ihre Anzahl an.
Lösung anzeigen
\(2^0+2^1+2^2+2^3 = 1+2+4+8\) = 15 Wörter
Ein DEA hat 6 Zustände. Er liest nacheinander die Vorgeschichten \(a^0, a^1, a^2, \dots\). Nennen Sie die Mindestzahl an Vorgeschichten, bei der sicher zwei im selben Zustand enden.
Lösung anzeigen
6 Zustände + 1 = 7 Vorgeschichten (\(a^0\) bis \(a^6\))
Genau das nutzt der Beweis, dass kein DEA \(\{a^nb^n\}\) erkennt.