Automaten Flashcards
Welche Automaten gibt es?
– endlicher Automat (EA)
– deterministischer endlicher Automat (DEA)
– nichtdeterministischer endlicher Automat (NEA)
– Kellerautomat
– (Turing-Maschine)
Was ist ein endlicher Automat?
Die Menge der Eingabe, Zustände und Ausgaben sind endlich.
Es wird etwas eingegeben und danach etwas ausgegeben.
Die können nicht- und deterministisch sein.
Es gibt Akzeptoren und Transduktoren.
Was ist ein Akzeptor und was ist ein Transduktor?
Akzeptor: Ein Automat ohne Ausgabe.
Transduktor: Ein Automat mit Ausgabe.
Wie definiert/erstellt man einen endlichen Akzeptor?
Durch ein 5-Tupel:
Z, die Menge an Zustände
∑, das Eingabealphabet, eine Menge an Symbolen
z0 ∈ Z, der Startzustand
Ze, die Menge an Endzustände mit Ze ∈ Z
δ : Z x ∑ → Z, die Zustandsübergangsfunktion
Wann gilt ein Wort, das von einem endlichen Automaten verarbeitet werden soll als akzeptiert?
Wenn es den Automaten vom Start- in einen Endzustand überführt.
Wie definiert/erstellt man einen endlichen Transduktor?
Durch ein 7-Tupel:
Z, die Menge an Zustände
∑, das Eingabealphabet, eine Menge an Symbolen
Y, die Menge an möglichen Ausgaben
z0 ∈ Z, der Startzustand
Ze, die Menge an Endzustände mit Ze ∈ Z
δ : Z x ∑ → Z, die Zustandsübergangsfunktion, die jedem Zustand und Eingabezeichen einen Folgezustand zuweist
λ : Z x ∑ → Y, die Ausgabefunktion die jedem Zustand und Eingabezeichen eine Ausgabe zuweist
Was ist das besondere an einem nichtdeterministischen endlichen Automaten?
Er kann mit der gleichen Eingabe mehrere Möglichkeiten haben in welchen Zustand er überführt wird. Das bringt Vorteile für die Problemlösung mit Grammatiken.
Welchen Automat nutzt man für die Umsetzung von nicht-regulären Grammatiken?
Kellerautomaten,
sie besitzen einen (Keller-)Speicher, der einem dabei hilft zu zählen.
Wie definiert/erstellt man einen Kellerautomaten?
Durch ein 7-Tupel:
Z, die Menge an Zustände
∑, das Eingabealphabet, eine Menge an Symbolen
K, die Menge an möglichen Kellerinhalten
z0 ∈ Z, der Startzustand
Ze, die Menge an Endzustände mit Ze ∈ Z
δ : Z x ∑ x K → Z, die Zustandsübergangsfunktion, die jedem Zustand, Eingabezeichen und Kellerelement einen Folgezustand zuweist
λ : Z x ∑ x K → K, die Ausgabefunktion die jedem Zustand, Eingabezeichen und Kellerinhalt einen Kellerinhalt zuweist
Wann gilt ein Wort, das von einem Kellerautomaten bearbeitet werden soll als akzeptiert?
Wenn es den Automaten vom Startzustand in einen beliebigen Endzustand überführt.
Was sind die Nachteile von Kellerautomaten?
Das Eingabeband kann nur in eine Richtung bewegt werden.
Es kann nur das oberste Kellerelement gelesen werden
Aus was besteht eine Turing-Maschine?
– Schaltwerk mit einer festen Anzahl von Zuständen
– ein unendlich langes Band als Speicher
– einem Schreib-Lese-Kopf
Was passiert nachdem der Schreib-Lese-Kopf zu einer neuen Zelle kommt? (Turing-Maschine)
Aus dem derzeitigen Zustand und dem gelesenem Zeichen bestimmt das Schaltwerk aus einer Tabelle:
– den nächsten Zustand
– die Richtung, wohin der Schreib-Lese-Kopf sich hinbewegen soll
– ein neues Zeichen zur Ersetzung
