Filter:
01
Notation
Eingabealphabet
→ klicken zum Umdrehen
Antwort
\(\Sigma=\{a,\,b\}\)endliche Menge der erlaubten Eingabezeichen
02
Notation
Leeres Wort
→ klicken zum Umdrehen
Antwort
\(\varepsilon\)Wort ohne Zeichen; akzeptiert, wenn der Start ein Endzustand ist
03
Notation
Alle Wörter über Σ
→ klicken zum Umdrehen
Antwort
\(\Sigma^*\)alle Zeichenfolgen aus \(\Sigma\), einschließlich \(\varepsilon\)
04
Notation
Sprache eines Automaten
→ klicken zum Umdrehen
Antwort
\(L(A)=\{\,w\in\Sigma^*\mid A \text{ akzeptiert } w\,\}\)Bedingung in Worten nach dem senkrechten Strich
05
Notation
Startzustand im Graphen
→ klicken zum Umdrehen
Antwort
→ ◯Pfeil ohne Ausgangszustand zeigt auf den Startzustand
06
Notation
Endzustand im Graphen
→ klicken zum Umdrehen
Antwort
◎Doppelkreis; beliebig viele, auch keiner
07
Notation
Fehlerzustand zF weglassen
→ klicken zum Umdrehen
Antwort
nur mit Vermerk„Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.“
08
Notation
Anzahl der Übergänge
→ klicken zum Umdrehen
Antwort
\(|Z|\cdot|\Sigma|\)so viele Pfeile hat ein vollständiger DEA
09
Notation
Übergangstabelle
→ klicken zum Umdrehen
Antwort
Zeile × Spalte → FolgezustandZeile = Zustand, Spalte = Zeichen; → Start, doppelt unterstrichen = Ende
10
Notation
Pfeil eines Mealy-Automaten
→ klicken zum Umdrehen
Antwort
\(e\,/\,a\)Eingabe \(e\in\Sigma\) lesen, Ausgabe \(a\in\Omega^*\) erzeugen
11
Notation
Ausgabealphabet
→ klicken zum Umdrehen
Antwort
\(\Omega\)mögliche Ausgabezeichen; \(\varepsilon\) = keine Ausgabe
12
Notation
Ein Schritt im Code
→ klicken zum Umdrehen
Antwort
zustand = delta[zustand][spalte(c)];Tabellenzugriff statt switch; −1 für Zeichen außerhalb von Σ abfangen
13
Notation
Grenze eines DEA
→ klicken zum Umdrehen
Antwort
\(k\) Zustände \(\Rightarrow\) höchstens \(k\) Vorgeschichtenmehr kann ein DEA nicht unterscheiden
14
Notation
Nicht reguläre Sprache
→ klicken zum Umdrehen
Antwort
\(L=\{a^nb^n\mid n\ge 0\}\)kein DEA erkennt sie — Beweis mit dem Schubfachprinzip
15
Begriff
Zustand
→ klicken zum Umdrehen
Antwort
Situation, in der sich ein System gerade befindet und die andauert, z. B. „Schranke offen“.
16
Begriff
Eingabe
→ klicken zum Umdrehen
Antwort
Ereignis von außen, auf das der Automat reagiert; steht als Beschriftung am Pfeil.
17
Begriff
Übergang
→ klicken zum Umdrehen
Antwort
Wechsel vom aktuellen Zustand in den Folgezustand, ausgelöst durch eine Eingabe.
18
Begriff
Zustandsfolge
→ klicken zum Umdrehen
Antwort
Die Zustände, die beim Lesen eines Worts nacheinander durchlaufen werden.
19
Begriff
DEA
→ klicken zum Umdrehen
Antwort
Deterministischer endlicher Automat: liest ein Wort Zeichen für Zeichen und akzeptiert es oder lehnt es ab.
20
Begriff
Deterministisch
→ klicken zum Umdrehen
Antwort
Für jeden Zustand und jedes Zeichen gibt es genau einen Folgezustand.
21
Begriff
Akzeptieren
→ klicken zum Umdrehen
Antwort
Der DEA ist nach dem letzten Zeichen in einem Endzustand — Zwischenstände zählen nicht.
22
Begriff
Vollständiger Automat
→ klicken zum Umdrehen
Antwort
Aus jedem Zustand führt für jedes Zeichen ein Pfeil; ggf. in den Fehlerzustand.
23
Begriff
Bedeutung eines Zustands
→ klicken zum Umdrehen
Antwort
Was der Automat in diesem Zustand über das bisher gelesene Wort „weiß“, z. B. „endet auf ab“.
24
Begriff
Gegenprobe
→ klicken zum Umdrehen
Antwort
Wörter aus der Beschreibung müssen akzeptiert, alle anderen abgelehnt werden.
25
Begriff
Grenzfälle
→ klicken zum Umdrehen
Antwort
Testwörter wie ε, das kürzeste Wort und Wörter, die knapp scheitern.
26
Begriff
Mealy-Automat
→ klicken zum Umdrehen
Antwort
Endlicher Automat mit Ausgabe an jedem Übergang; übersetzt ein Eingabewort in ein Ausgabewort.
27
Begriff
Ausgabewort
→ klicken zum Umdrehen
Antwort
Die Ausgaben aller Übergänge hintereinander gelesen; ε fällt dabei weg.
28
Begriff
Ablaufprotokoll
→ klicken zum Umdrehen
Antwort
Tabelle mit Schritt, Zustand, Eingabe, Ausgabe und Folgezustand je gelesenem Zeichen.
29
Begriff
Reguläre Sprache
→ klicken zum Umdrehen
Antwort
Eine Sprache, für die es einen DEA gibt, der sie erkennt.
30
Begriff
Vorgeschichte
→ klicken zum Umdrehen
Antwort
Das bisher gelesene Anfangsstück eines Worts; gleicher Zustand heißt: ab jetzt gleiche Behandlung.
Keine Karten in dieser Auswahl.
Gehen Sie den Stapel dreimal durch: erst alle Karten, dann nur die Notation, zuletzt nur die ungelernten. Sagen Sie die Antwort laut — bei Notationen mit einem eigenen kleinen Beispiel —, bevor Sie umdrehen.