⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠
Text Elements
Deterministischer Endlicher Automat (DEA)
eindeutig bestimmt (für die gleiche Eingabe wird immer der gleiche Übergang gewählt) endliche Anzahl von Zuständen
Definition
Zeichen
Erklärung
Menge aller Zustände
Menge aller Eingabezeichen (Eingabealphabet)
Übergnagsfunktion
Startzustand
Menge der Endzustand (Teilmenge der aller Zustände)
Der DEA wird mit einem Pentupel definiert.
Darstellung
q0
Start
0
q1
1
1
Mealy-Automat
Erweiterung
Erweiterung des DEA um
Ausgabealphabet
Symbolik:
Eingabe
/
Ausgabe
z0
z1
Ω = {A, B}
Definition:
a/B
Endzustand
Deterministischer Kellerautomat (DKA)
Der DKA erweitert den Mealy-Automaten um einen
Kellerspeicher
Im Kellerspeicher können Zeichen aus dem
Kelleralphabet
abgelegt
werden.
Definition
= Γ = {A, #}
Kelleralphabet
Bei jedem Zustandsübergang wird das oberste Kellerzeichen gefolgt vom aktuellen Eingabezeichen notiert. Das vom Speicher gelesene Zeichen
wird dabei aus dem Keller entfernt
.
Nach dem Übergang können beliebig viele Zeichen auf dem Kellerspeicher gelegt werden.
Der Keller hat ein Zeichen im Keller.
Vorbelegungszeichen
. Jenes ist initial das unterste
sind Übergänge, bei denen kein Eingabezeichen notwendig
ε-Übergänge
ist. Es können nicht zwei ε-Übergänge mit dem selben Kellerzeichen auf einander Folgen.
Akzeptierende Automaten
Symbolik
(
Kellerzeichen
):
,
Eingabezeichen
(Wenn es gelesen wurde, muss es wieder in den Keller
gelegt werden)
Kellerzeichen
Das Kellerzeichen, dass oben auf dem Keller liegen muss.
Die Kellerzeichen, die auf dem Kellerspeicher gelegt werden.
Eine leere Ausgabe wird mit dem Zeichen ε gekennzeichnet.
Embedded files
22ad1e6ec6f10b2de56f8eb061a99d3dc42a8c58: 7809a38d577f4a8c4755b5963b7204abc9e56134: ca3a3ea467f7d4d0a5e2ade5fe48b47cecbf32ed: b3872bac2883c4fa2819cc96e2895a321c6a9f4a: 0597a6fbc5cb0e3c4cca50ba180f1052007b52c1: