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; auch: keine Ausgabe, nichts lesen, nichts ablegen
03
Notation
Alle Wörter über Σ
→ klicken zum Umdrehen
Antwort
\(\Sigma^*\)alle Zeichenfolgen aus Σ, einschließlich ε
04
Notation
Sprache eines Automaten
→ klicken zum Umdrehen
Antwort
\(L(A)\)Menge aller Wörter, die A akzeptiert
05
Notation
Übergänge eines vollständigen DEA
→ klicken zum Umdrehen
Antwort
\(|Z|\cdot|\Sigma|\)je Zustand und Zeichen genau ein Pfeil
06
Notation
Mealy-Übergang
→ klicken zum Umdrehen
Antwort
e / ae lesen, a ausgeben; a darf ein Wort über Ω oder ε sein
07
Notation
Ausgabealphabet
→ klicken zum Umdrehen
Antwort
\(\Omega\)Zeichen, die ein Mealy-Automat ausgeben kann
08
Notation
Kelleralphabet
→ klicken zum Umdrehen
Antwort
\(\Gamma=\{A,\,\#\}\)Zeichen, die im Keller liegen dürfen; # = Vorbelegung
09
Notation
Kellerübergang
→ klicken zum Umdrehen
Antwort
(X,e):Woberstes Zeichen X und Eingabe e: X entfernen, W ablegen (rechtes Zeichen zuerst)
10
Notation
ε-Übergang
→ klicken zum Umdrehen
Antwort
(#,ε):#Zustandswechsel ohne Lesen — typisch in den Endzustand, wenn # oben liegt
11
Notation
Grammatik
→ klicken zum Umdrehen
Antwort
N, T, Startsymbol, ProduktionsregelnNotation der Anlage; Nichtterminale groß, Terminale klein
12
Notation
Ableitung
→ klicken zum Umdrehen
Antwort
\(S\Rightarrow aA\Rightarrow ab\)⇒ verbindet Satzformen; → steht in Regeln
13
Notation
Erzeugte Sprache
→ klicken zum Umdrehen
Antwort
\(L(G)=\{w\in T^*\mid S\Rightarrow^* w\}\)alle Wörter aus Terminalen, die aus S ableitbar sind
14
Notation
Reguläre Regelformen
→ klicken zum Umdrehen
Antwort
A → aB | a | εNichtterminal höchstens einmal und ganz rechts
15
Begriff
Zustand
→ klicken zum Umdrehen
Antwort
Das, was ein Automat über das bisher Gelesene weiß — sein ganzes Gedächtnis.
16
Begriff
Endzustand
→ klicken zum Umdrehen
Antwort
Zustand mit Doppelkreis; das Wort wird akzeptiert, wenn der Automat nach dem letzten Zeichen dort ist.
17
Begriff
Fehlerzustand zF
→ klicken zum Umdrehen
Antwort
Zustand ohne Ausweg; darf im Graphen fehlen, wenn darauf hingewiesen wird.
18
Begriff
Deterministisch
→ klicken zum Umdrehen
Antwort
Je Zustand (beim Kellerautomaten: und oberstem Kellerzeichen) und Zeichen höchstens ein Übergang.
19
Begriff
Mealy-Automat
→ klicken zum Umdrehen
Antwort
Automat mit Ausgabe an den Übergängen; hat keine Endzustände.
20
Begriff
Schubfachprinzip
→ klicken zum Umdrehen
Antwort
Mehr Vorgeschichten als Zustände → zwei davon enden im selben Zustand.
21
Begriff
Reguläre Sprache
→ klicken zum Umdrehen
Antwort
Sprache, die ein DEA erkennt — gleichwertig: die eine reguläre Grammatik erzeugt.
22
Begriff
Kellerautomat
→ klicken zum Umdrehen
Antwort
Automat mit Stapelspeicher; erkennt z. B. {aⁿbⁿ} und Klammerausdrücke.
23
Begriff
Kellerplan
→ klicken zum Umdrehen
Antwort
Entwurfsidee: welches Zeichen legt was ab, welches entfernt was — vor den Übergängen festlegen.
24
Begriff
Nichtterminal
→ klicken zum Umdrehen
Antwort
Hilfssymbol einer Grammatik, das noch ersetzt wird (Großbuchstabe).
25
Begriff
Terminal
→ klicken zum Umdrehen
Antwort
Zeichen der fertigen Wörter (Kleinbuchstabe oder Ziffer).
26
Begriff
Satzform
→ klicken zum Umdrehen
Antwort
Zwischenergebnis einer Ableitung aus Terminalen und Nichtterminalen.
27
Begriff
Ableitungsbaum
→ klicken zum Umdrehen
Antwort
Baum mit Wurzel S; die Blätter von links nach rechts ergeben das Wort.
28
Begriff
Kontextfreie Grammatik
→ klicken zum Umdrehen
Antwort
Links jeder Regel genau ein Nichtterminal, rechts beliebig — passt zum Kellerautomaten.
29
Begriff
Mehrdeutig
→ klicken zum Umdrehen
Antwort
Ein Wort hat zwei verschiedene Ableitungsbäume, z. B. mit S → SS | ab.
30
Begriff
Umwandlung DEA ↔ Grammatik
→ klicken zum Umdrehen
Antwort
Zustand = Nichtterminal, Pfeil = Regel A → aB, Endzustand = Regel A → ε.
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.