MINT lernen

Abituraufgaben: Automaten

Ein Eintrittsautomat mit Rückgeld und Nachrichten mit geschachtelten Rahmen — Mealy, Keller und Grammatik in der Notation der Anlage.

Dein Fortschritt:
0 / 0 Aufgaben
1

Eintrittsautomat im Museum

14 BEAFB I–II

Ein Automat verkauft Eintrittskarten zu 3 €. Er nimmt 1-€-Münzen (e) und 2-€-Münzen (z) an und gibt eine Karte (T) und gegebenenfalls 1 € Rückgeld (R) aus. Er wird als Mealy-Automat mit \(\Sigma=\{e,\,z\}\) und \(\Omega=\{T,\,R\}\) modelliert; der Zustand ist das bisherige Guthaben.

Guthabenez
0 €1 € / ε2 € / ε
1 €2 € / ε0 € / T
2 €0 € / T0 € / TR
  1. Geben Sie das Ausgabewort zur Eingabe ezzee und das Guthaben am Ende an. (3 BE)
  2. Zeichnen Sie den Übergangsgraphen in der Notation der Anlage. (4 BE)
  3. Erläutern Sie, warum der Mealy-Automat keine Endzustände hat, und vergleichen Sie ihn mit einem DEA für „genau 3 € eingeworfen“. (3 BE)
  4. Der Eintritt steigt auf 4 €. Erweitern Sie den Automaten und geben Sie die Übergangstabelle an. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Ablaufprotokoll: Guthaben, Eingabe, Ausgabe, neues Guthaben.
Hinweis zu Aufgabe b)
Je Zustand zwei Pfeile — mit „Eingabe / Ausgabe“ beschriftet.
Hinweis zu Aufgabe c)
Was ist das Ergebnis eines Mealy-Automaten, was das eines DEA?
Hinweis zu Aufgabe d)
Ein zusätzlicher Zustand für 3 € Guthaben; überlegen Sie, wann R ausgegeben wird.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

0 € –e/ε→ 1 € –z/T→ 0 € –z/ε→ 2 € –e/T→ 0 € –e/ε→ 1 €

Ausgabewort: TT, Guthaben am Ende 1 €.

Erwartungshorizont zu Aufgabe b)
Lösung: Eintrittsautomat (Guthaben 0 €, 1 €, 2 €)
0 € 1 € 2 € e / ε z / T e / ε z / ε e / Tz / TR

Vollständig: Jeder der drei Zustände hat je einen Pfeil für e und für z.

Erwartungshorizont zu Aufgabe c)

Ein Mealy-Automat liefert als Ergebnis ein Ausgabewort — er entscheidet nicht über Annahme, deshalb braucht er keine Endzustände. Ein DEA für „genau 3 € eingeworfen“ hätte Zustände für 0 bis 3 € (und zF bei Überzahlung), den Endzustand 3 € und keine Ausgaben: Er beantwortet nur ja oder nein.

Erwartungshorizont zu Aufgabe d)
Guthabenez
0 €1 € / ε2 € / ε
1 €2 € / ε3 € / ε
2 €3 € / ε0 € / T
3 €0 € / T0 € / TR

Neuer Zustand 3 €; eine Karte gibt es jetzt erst bei 4 €, Rückgeld nur bei 3 € + 2 €.

2

Nachrichten mit Rahmen

22 BEAFB II–III

Ein Messgerät verschickt Nachrichten: Die Daten (d) stehen in mehreren Rahmen, jeder Rahmen wird mit o geöffnet und mit s geschlossen, z. B. oodss. Das Format wird durch die Grammatik G festgelegt:

N = {S, T}
T = {o, d, s}
Startsymbol: S
Produktionsregeln:
S → oSs | oTs
T → dT | d
  1. Wenden Sie G an: Geben Sie eine Ableitung für ooddss an. (3 BE)
  2. Beschreiben Sie L(G) in Mengenschreibweise und begründen Sie, dass G kontextfrei, aber nicht regulär ist. (3 BE)
  3. Entwickeln Sie einen deterministischen Kellerautomaten in der Notation der Anlage, der L(G) erkennt, und geben Sie die Konfigurationsfolge für oodss an. (6 BE)
  4. Beweisen Sie, dass kein DEA die Sprache L(G) erkennt. (6 BE)
  5. Implementieren Sie in Java eine Methode boolean gueltig(String w), die prüft, ob w zu L(G) gehört. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
S wird zweimal verwendet, dann T.
Hinweis zu Aufgabe b)
Wie viele o, d und s dürfen es jeweils sein? Welche Regelform hat S → oSs?
Hinweis zu Aufgabe c)
Jedes o legt ein Symbol ab; d ändert den Keller nicht; jedes s entfernt eines.
Hinweis zu Aufgabe d)
Schubfachprinzip mit den Vorgeschichten oⁱ.
Hinweis zu Aufgabe e)
Da nur ein Kellersymbol vorkommt, genügen drei Zähler für o, d und s.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

S ⇒ oSs ⇒ ooTss ⇒ oodTss ⇒ ooddss

Erwartungshorizont zu Aufgabe b)

\(L(G)=\{o^nd^ms^n\mid n,m\ge 1\}\). Links steht in jeder Regel genau ein Nichtterminal — kontextfrei. S → oSs hat das Nichtterminal in der Mitte, also hat die Regel nicht die reguläre Form (dass die Sprache nicht regulär ist, zeigt erst d).

Erwartungshorizont zu Aufgabe c)

Σ = {o, d, s}, Γ = {A, #}, Endzustand S4.

vonÜbergangnach
S0(#,o):A#S1
S1(A,o):AAS1
S1(A,d):AS2
S2(A,d):AS2
S2(A,s):εS3
S3(A,s):εS3
S3(#,ε):#S4

(S0, oodss, #) → (S1, odss, A#) → (S1, dss, AA#) → (S2, ss, AA#) → (S3, s, A#) → (S3, ε, #) → (S4, ε, #): akzeptiert.

Deterministisch: Der ε-Übergang von S3 hat # oben, alle anderen Übergänge von S3 A.

Erwartungshorizont zu Aufgabe d)

Annahme: Ein DEA mit k Zuständen erkennt L(G). Von den Vorgeschichten \(o^1,\dots,o^{k+1}\) enden zwei, \(o^i\) und \(o^j\) mit \(i<j\), im selben Zustand (Schubfachprinzip). Hängt man \(ds^i\) an, endet der DEA bei \(o^ids^i\) und \(o^jds^i\) im selben Zustand — beide werden gleich beurteilt. Aber \(o^ids^i\in L(G)\) und \(o^jds^i\notin L(G)\). Widerspruch: Kein DEA erkennt L(G).

Erwartungshorizont zu Aufgabe e)
Java
// L = { o^n d^m s^n | n, m >= 1 }; der Zähler ersetzt den Keller mit A-Symbolen
public static boolean gueltig(String w) {
    int i = 0;
    int n = 0;
    while (i < w.length() && w.charAt(i) == 'o') { n++; i++; }
    int m = 0;
    while (i < w.length() && w.charAt(i) == 'd') { m++; i++; }
    int k = 0;
    while (i < w.length() && w.charAt(i) == 's') { k++; i++; }
    return i == w.length() && n >= 1 && m >= 1 && k == n;
}

Test: oodss, odds → true; ooddds, os, oodssd → false.