W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


Zweikellerautomat

*** Shopping-Tipp: Zweikellerautomat

Der Begriff '''Zweikellerautomat''' steht in der Theoretische Informatik Theoretischen Informatik für ein besonderes Automat (Informatik) Automatenmodell. Er hat insbesondere für eine einheitliche Darstellung von Automaten-Charakterisierungen der Sprachenklassen der Chomsky-Hierarchie und anderen Klassen eine besondere Bedeutung erlangt. So lassen sich die klassischen Begriffe Turingmaschine, Linear beschränkter Automat, Kellerautomat und Endlicher Automat mit speziellen Einschränkungen einheitlich darstellen. Darüberhinaus gestattet er die Charakterisierung der von Elias Dahlhaus und Manfred Warmuth eingeführten Klasse der wachsend kontextsensitive Sprache wachsend kontextsensitiven Sprachen. In der Literatur werden zwei verschiedene Modelle betrachtet: # Der Zweikellerautomat liest von einem Extra-Eingabeband und kann dabei zwei Kellerspeicher zum Speichern und Lesen nutzen. Als Abkürzung wird hier meist 2-PDA verwendet. # Der Zweikellerautomat bekommt seine Eingabe direkt im Keller: Das erste Zeichen steht dabei oben. Dieses Modell ist das jüngere Modell. Als Abkürzung wird hier meist TPDA (engl. Two-PushDown-Automaton) verwendet. In beiden Fällen ergibt sich, dass der Zweikellerautomat ohne weitere Einschränkung bereits turing-mächtig ist. Im ersten Fall ist vor allem der Automat mit Realzeiteingabe untersucht worden. Diese Eingabe entspricht dem normalen Kellerautomaten, der nur einen Keller benutzt. Im zweiten Fall wurden verschiedene Einschränkungen definiert, mit denen sich einheitlich verschiedene Sprachklassen charakterisieren lassen. So werden hier beschränkte und schrumpfende Zweikellerautomaten betrachtet. Weiterhin verbietet man das Schreiben im Eingabekeller, das führt zum normalen Kellerautomat Kellerautomaten. Das Verbot des Schreibens in beiden Kellern führt schließlich zum endlicher Automat endlichen Automaten.

Definition
Ein '''Zweikellerautomat (TPDA)''' ist ein nichtdeterministischer Automat, der während seiner Arbeit auf zwei Kellerspeicher zugreifen kann und seine Eingabe in einem der beiden Kellerspeicher erhält. Mathematisch wird ein solcher Automat M beschrieben durch ein Siebentupel M=(Q,\Sigma,\Gamma,q_0,\bot,F,\delta). Im einzelnen wird dabei durch * Q eine endliche Menge bezeichnet: die Zustandsmenge * \Sigma ein (endliches) Alphabet, das Eingabealphabet bezeichnet * \Gamma ein weiteres endliches Alphabet, das Arbeitsalphabet bezeichnet: \Sigma\subset\Gamma und \Gamma\cap Q=\emptyset * q_0 den Startzustand mit q_0\in Q * F die Endzustände mit F\subseteq Q * \delta die totale Abbildung von Q\times\Gamma\times\Gamma in die endlichen Teilmengen von Q\times\Gamma^*\times\Gamma^*. Wenn die Menge \delta(q,A,B) stets höchstens einelementig ist, heißt der TPDA ''deterministisch''; hier hat sich die Abkürzung DTPDA eingebürgert. Jede Situation einer Berechnung eines TPDA wird durch seine Konfiguration vollständig beschrieben: Eine Konfiguration kann als Wort über dem Alphabet Q\cup\Gamma beschrieben werden; in diesem Fall ist es üblich, die Konfigurationen mit dem folgenden regulären Ausdruck zu beschreiben: * \Gamma^* Q \Gamma^* Hierbei steht der erste Teil des Wortes vor dem Zustandssymbol für den linken Keller und der zweite für den rechten Keller. So liest der Automat im linken Keller von rechts nach links und im rechten von links nach rechts. (Das Zustandssysmbol zwischen den beiden Kellerinhalten mag hier intuitiv als Lese-Schreibkopf interpretiert werden.) Daher wird in der Startkonfiguration im linken Keller die Eingabe rückwärts notiert: * \bot w_n\cdots w_1q\bot ist somit die ''Startkonfiguration''. Die Überführungsfunktion wird jetzt in folgender Weise angewandt: * Wenn \gamma_0AqB\gamma_1 die aktuelle Konfiguration des TPDA ist und \delta(q,A,B)=\{(q_1,\alpha_1,\beta_1),(q_2,\alpha_2,\beta_2),\ldots,(q_m,\alpha_m,\beta_m)\} gilt, dann stellt für jedes i\in\{1,2,\ldots,m\} die Konfiguration \gamma_0\alpha_iq_i\beta_i\gamma_1 eine mögliche ''Nachfolgekonfiguration'' von \gamma_0AqB\gamma_1 dar. Eine Eingabewort w\in\Sigma^* wird von einem TPDA ''Akzeptieren (Automaten- und Komplexitätstheorie) akzeptiert'', wenn es eine Folge von Konfigurationen gibt, die durch wiederholtes Anwenden der Überführungsfunktion gebildet wird, mit der Eigenschaft: die letzte Konfiguration besteht nur noch aus einem Zeichen, dieses Zeichen ist ein Endzustand aus F. Es wird gelegentlich auch gestattet, dass die Keller nicht leer sein müssen. Das TPDA-Modell ist hier ausreichend robust. Für die Einschränkungen, die üblicherweise betrachtet werden, wird der Begriff der Bewertungsfunktion (Formale Sprachen) Bewertungsfunktion benötigt: Eine ''Bewertungsfunktion'' ist ein Monoid-Homomorphismus vom Monoid freien Monoid über \Gamma\cup Q in die natürliche Zahl natürlichen Zahlen (mit 0): :h:((\Gamma\cup Q)^*,\circ)\rightarrow(\mathbb{N},+), :h(\varepsilon) = 0 :für alle Wörter v,w\in(\Gamma\cup Q)^* gilt: h(v)+h(w)=h(v\circ w). Hier bezeichnet \varepsilon das leeres Wort leere Wort und \circ die ''Konkatenation''. * Ein TPDA M=(Q,\Sigma,\Gamma,q_0,\bot,F,\delta) heißt ''schrumpfend'', wenn es eine Bewertung h gibt so dass für die Überführungsfunktion \delta gilt: Wenn (q',\alpha,\beta)\in\delta(q,A,B) dann ist h(q'\circ\alpha\circ\beta)< h(q\circ A\circ B). * Ein TPDA M=(Q,\Sigma,\Gamma,q_0,\bot,F,\delta) heißt ''beschränkt'', wenn es eine Bewertung h gibt so dass für die Überführungsfunktion \delta gilt: Wenn (q',\alpha,\beta)\in\delta(q,A,B) dann ist h(q'\circ\alpha\circ\beta)\le(q\circ A\circ B).

Charakterisierungen
# Die rekursiv aufzählbare Sprache rekursiv aufzählbaren Sprachen werden vom Modell TPDA charakterisiert. # Die rekursiv aufzählbare Sprache rekursiv aufzählbaren Sprachen werden vom Modell DTPDA charakterisiert. # Die kontextsensitive Sprache kontextsensitiven Sprachen werden von beschränkten TPDA charakterisiert. # Die deterministisch kontextsensitive Sprache deterministisch kontextsensitiven Sprachen werden von beschränkten DTPDA charakterisiert. # Die wachsend kontextsensitive Sprache wachsend kontextsensitiven Sprachen werden von schrumpfenden TPDA charakterisiert. # Die Church-Rosser-Sprache Church-Rosser-Sprachen werden von schrumpfenden DTPDA charakterisiert. # Die kontextfreie Sprache kontextfreien Sprachen werden von TPDA charakterisiert, die nur im rechten Keller schreiben dürfen. # Die deterministisch kontextfreie Sprache deterministisch kontextfreien Sprachen werden von DTPDA charakterisiert, die nur im rechten Keller schreiben dürfen. # Die reguläre Sprache regulären Sprachen werden von TPDA charakterisiert, die in ihren Kellern nicht schreiben dürfen. # Die reguläre Sprache regulären Sprachen werden von DTPDA charakterisiert, die in ihren Kellern nicht schreiben dürfen.

Ausblicke
Wenn wir in dem Modell weitere Keller hinzunehmen, so ergibt sich für den schrumpfenden Fall, dass er die nichtdeterministischen quasi Realzeit-Sprache quasi Realzeit-Sprachen (\mathbf{Q}) akzeptiert. kategorie:Komplexitätstheorie kategorie:Automatentheorie kategorie:Formale Sprachen kategorie:Theoretische Informatik

*** Shopping-Tipp: Zweikellerautomat




[Der Artikel zu Zweikellerautomat stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels Zweikellerautomat zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite