www.wikidata.de-de.nina.az

Büchi Automat Der nach dem Schweizer Mathematiker Julius Richard Büchi ist eine spezielle Form des ω Automaten Dieser Au

Büchi-Automat

Der Büchi-Automat (nach dem Schweizer Mathematiker Julius Richard Büchi) ist eine spezielle Form des ω-Automaten. Dieser Automatentyp kann benutzt werden, um sowohl Sprachen über unendlichen Wörtern als auch über unendlichen Bäumen zu erkennen.

Büchi-Automaten zur Worterkennung Bearbeiten

Nichtdeterministischer Büchi-Automat zur Worterkennung Bearbeiten

Ein nichtdeterministischer Büchi-Automat (NBA) ist ein 5-Tupel wobei gilt:

  • ist eine endliche Menge von Zuständen, die Zustandsmenge
  • ist eine endliche Menge von Symbolen, das Eingabealphabet
  • ist die Übergangsrelation mit
  • ist eine endliche Menge von Zuständen mit , die Startzustandsmenge
  • ist eine endliche Menge von Zuständen mit , die Endzustandsmenge

Deterministischer Büchi-Automat zur Worterkennung Bearbeiten

Ein deterministischer Büchi-Automat (DBA) ist ein 5-Tupel wobei gilt:

  • ist eine endliche Menge von Zuständen, die Zustandsmenge
  • ist eine endliche Menge von Symbolen, das Eingabealphabet
  • ist die Übergangsfunktion mit
  • ist der Startzustand mit
  • ist eine endliche Menge von Zuständen mit , die Endzustandsmenge

Deterministische Büchi-Automaten sind nicht unter Komplementbildung abgeschlossen.

Akzeptanzverhalten Bearbeiten

Ein unendliches Wort wird vom (nichtdeterministischen) Büchi-Automaten akzeptiert genau dann, wenn für einen (deterministisch: den) zugehörigen (unendlichen) Pfad gilt:

  • für alle
  • es gibt unendlich viele mit .

Weniger formal bedeutet das: Wird ein Endzustand unendlich oft durchlaufen, dann akzeptiert der Büchi-Automat das Eingabewort.

Die von einem Büchi-Automaten akzeptierte ω-Sprache (Menge unendlicher Wörter) ist . Diese ω-Sprache heißt dann Büchi-erkennbar. Jede Büchi-erkennbare ω-Sprache kann durch dargestellt werden, wobei und reguläre Sprachen für alle sind. Aufgrund dieses engen Zusammenhangs zu regulären Sprachen werden Büchi-erkennbare ω-Sprachen auch als ω-reguläre Sprachen bezeichnet. Damit ist der nichtdeterministische Büchi-Automat äquivalent zum Muller-Automaten, Rabin-Automaten, Streett-Automaten und zum Parity-Automaten.

Eigenschaften Bearbeiten

Die Möglichkeit der Potenzmengenkonstruktion, d. h. der Algorithmus, um aus einem nichtdeterministischen einen deterministischen Automaten zu machen, ist auf Büchi-Automaten nicht anwendbar. Die Menge der durch deterministische Büchi-Automaten erkennbaren Sprachen ist echt kleiner als die Menge der durch nichtdeterministische Büchi-Automaten erkennbaren Sprachen. Zum Beispiel gibt es keinen deterministischen Büchi-Automaten, welcher die Sprache erkennt. Ein nichtdeterministischer Büchi-Automat für kann dagegen wie folgt grafisch angegeben werden:

Büchi-Automaten zur Baumerkennung Bearbeiten

Die Abkürzung BBA (englisch BTA) bezeichnet einen nichtdeterministischen Büchi-Automaten zur Baumerkennung; deterministische Büchi-Baumautomaten werden in der Regel nicht betrachtet. Als Eingabe dient ein unendlicher, gewurzelter Baum, dessen Knoten mit Symbolen aus dem Eingabealphabet beschriftet sind und bei dem jeder Knoten einen Ausgangsgrad hat. Der Aufbau des Büchi-Automaten zur Baumerkennung entspricht dem des NBA, wobei jedoch die Übergangsrelation eine andere Form hat:

.

Ein Lauf eines Büchi-Baumautomaten auf einem Eingabebaum ist ein Baum , der die gleichen Eigenschaften wie hat, bei dem die Knoten jedoch nicht mit Eingabesymbolen, sondern mit Zuständen beschriftet sind. Die Wurzel von ist mit einem Startzustand versehen, die restlichen Beschriftungen erfolgen gemäß der Übergangsrelation.

Akzeptanzverhalten Bearbeiten

Ein unendlicher Baum wird von einem Büchi-Baumautomaten akzeptiert genau dann, wenn für einen Lauf von auf gilt: Auf jedem unendlichen Pfad in kommen unendlich viele Endzustände vor. Die durch einen Büchi-Baumautomaten akzeptierten Bäume bilden eine Büchi-erkennbare Baumsprache. Die Klasse der Büchi-erkennbaren Baumsprachen ist unter Vereinigung abgeschlossen. Unter Komplement ist sie hingegen nicht abgeschlossen, wie sich mit einer Variante des Pumping-Lemmas zeigen lässt.

Jeder Büchi-Baumautomat lässt sich in einen äquivalenten Muller-Baumautomaten (MBA) umwandeln. Da die Klasse der muller-erkennbaren Baumsprachen unter Komplement abgeschlossen ist, sind Büchi-Baumautomaten schwächer als MBAs und als Paritätsbaumautomaten, welche äquivalent zu MBAs sind.

Co-Büchi-Automaten Bearbeiten

Ein (deterministischer) Co-Büchi-Automat ist ein 5-Tupel und unterscheidet sich von einem deterministischen Büchi-Automaten nur durch das Akzeptanzverhalten. Während ein Büchi-Automat ein Wort akzeptiert, falls immer wieder ein Endzustand besucht wird, so akzeptiert ein Co-Büchi-Automat ein Wort nur, wenn ab einem gewissen Punkt nur noch Endzustände besucht werden. Schreibt man dies etwas formaler auf, so sieht man, dass der Existenzquantor und der Allquantor vertauscht werden. Ein unendliches Wort wird vom (deterministischen) Büchi-Automaten bzw. Co-Büchi-Automaten akzeptiert genau dann, wenn für den zugehörigen eindeutigen Pfad gilt

  • mit (Büchi-Automat)
  • mit (Co-Büchi-Automat)

Literatur Bearbeiten

  • Wolfgang Thomas: Automata on Infinite Objects. In: Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science. Band B: Formal Models and Semantics. Elsevier Science Publishers u. a., Amsterdam u. a. 1990, ISBN 0-444-88074-7, S. 133–164.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Buchi Automat nach dem Schweizer Mathematiker Julius Richard Buchi ist eine spezielle Form des w Automaten Dieser Automatentyp kann benutzt werden um sowohl Sprachen uber unendlichen Wortern als auch uber unendlichen Baumen zu erkennen Inhaltsverzeichnis 1 Buchi Automaten zur Worterkennung 1 1 Nichtdeterministischer Buchi Automat zur Worterkennung 1 2 Deterministischer Buchi Automat zur Worterkennung 1 3 Akzeptanzverhalten 1 4 Eigenschaften 2 Buchi Automaten zur Baumerkennung 2 1 Akzeptanzverhalten 3 Co Buchi Automaten 4 LiteraturBuchi Automaten zur Worterkennung BearbeitenNichtdeterministischer Buchi Automat zur Worterkennung Bearbeiten Ein nichtdeterministischer Buchi Automat NBA ist ein 5 Tupel A Q S D I F displaystyle A left Q Sigma Delta I F right nbsp wobei gilt Q displaystyle Q nbsp ist eine endliche Menge von Zustanden die Zustandsmenge S displaystyle Sigma nbsp ist eine endliche Menge von Symbolen das Eingabealphabet D displaystyle Delta nbsp ist die Ubergangsrelation mit D Q S Q displaystyle Delta subseteq Q times Sigma times Q nbsp I displaystyle I nbsp ist eine endliche Menge von Zustanden mit I Q displaystyle I subseteq Q nbsp die Startzustandsmenge F displaystyle F nbsp ist eine endliche Menge von Zustanden mit F Q displaystyle F subseteq Q nbsp die EndzustandsmengeDeterministischer Buchi Automat zur Worterkennung Bearbeiten Ein deterministischer Buchi Automat DBA ist ein 5 Tupel A Q S d q 0 F displaystyle A left Q Sigma delta q 0 F right nbsp wobei gilt Q displaystyle Q nbsp ist eine endliche Menge von Zustanden die Zustandsmenge S displaystyle Sigma nbsp ist eine endliche Menge von Symbolen das Eingabealphabet d displaystyle delta nbsp ist die Ubergangsfunktion mit d Q S Q displaystyle delta colon Q times Sigma rightarrow Q nbsp q 0 displaystyle q 0 nbsp ist der Startzustand mit q 0 Q displaystyle q 0 in Q nbsp F displaystyle F nbsp ist eine endliche Menge von Zustanden mit F Q displaystyle F subseteq Q nbsp die EndzustandsmengeDeterministische Buchi Automaten sind nicht unter Komplementbildung abgeschlossen Akzeptanzverhalten Bearbeiten Ein unendliches Wort w a 1 a 2 a 3 displaystyle w a 1 a 2 a 3 ldots nbsp wird vom nichtdeterministischen Buchi Automaten A displaystyle A nbsp akzeptiert genau dann wenn fur einen deterministisch den zugehorigen unendlichen Pfad q 0 a 1 A q 1 a 2 A q 2 a 3 A q 3 displaystyle q 0 quad begin smallmatrix a 1 rightarrow A end smallmatrix quad q 1 quad begin smallmatrix a 2 rightarrow A end smallmatrix quad q 2 quad begin smallmatrix a 3 rightarrow A end smallmatrix quad q 3 quad ldots nbsp gilt q 0 I displaystyle q 0 in I nbsp q i a i 1 q i 1 D displaystyle q i a i 1 q i 1 in Delta nbsp fur alle i displaystyle i nbsp es gibt unendlich viele i displaystyle i nbsp mit q i F displaystyle q i in F nbsp Weniger formal bedeutet das Wird ein Endzustand unendlich oft durchlaufen dann akzeptiert der Buchi Automat das Eingabewort Die von einem Buchi Automaten A displaystyle A nbsp akzeptierte w Sprache Menge unendlicher Worter ist L w A w S w w wird von A akzeptiert displaystyle L omega A w in Sigma omega mid w text wird von A text akzeptiert nbsp Diese w Sprache heisst dann Buchi erkennbar Jede Buchi erkennbare w Sprache kann durch i 1 m U i V i w displaystyle cup i 1 m U i V i omega nbsp dargestellt werden wobei U i displaystyle U i nbsp und V i displaystyle V i nbsp regulare Sprachen fur alle i displaystyle i nbsp sind Aufgrund dieses engen Zusammenhangs zu regularen Sprachen werden Buchi erkennbare w Sprachen auch als w regulare Sprachen bezeichnet Damit ist der nichtdeterministische Buchi Automat aquivalent zum Muller Automaten Rabin Automaten Streett Automaten und zum Parity Automaten Eigenschaften Bearbeiten Die Moglichkeit der Potenzmengenkonstruktion d h der Algorithmus um aus einem nichtdeterministischen einen deterministischen Automaten zu machen ist auf Buchi Automaten nicht anwendbar Die Menge der durch deterministische Buchi Automaten erkennbaren Sprachen ist echt kleiner als die Menge der durch nichtdeterministische Buchi Automaten erkennbaren Sprachen Zum Beispiel gibt es keinen deterministischen Buchi Automaten welcher die Sprache L w a b w ϵ a kommt in w nur endlich oft vor displaystyle L w in a b omega backslash epsilon mid a text kommt in w text nur endlich oft vor nbsp erkennt Ein nichtdeterministischer Buchi Automat fur L displaystyle L nbsp kann dagegen wie folgt grafisch angegeben werden nbsp Buchi Automaten zur Baumerkennung BearbeitenDie Abkurzung BBA englisch BTA bezeichnet einen nichtdeterministischen Buchi Automaten zur Baumerkennung deterministische Buchi Baumautomaten werden in der Regel nicht betrachtet Als Eingabe dient ein unendlicher gewurzelter Baum dessen Knoten mit Symbolen aus dem Eingabealphabet S displaystyle Sigma nbsp beschriftet sind und bei dem jeder Knoten einen Ausgangsgrad k displaystyle k nbsp hat Der Aufbau des Buchi Automaten zur Baumerkennung entspricht dem des NBA wobei jedoch die Ubergangsrelation eine andere Form hat D Q S Q k displaystyle Delta subseteq Q times Sigma times Q k nbsp Ein Lauf eines Buchi Baumautomaten A displaystyle A nbsp auf einem Eingabebaum t displaystyle t nbsp ist ein Baum r displaystyle rho nbsp der die gleichen Eigenschaften wie t displaystyle t nbsp hat bei dem die Knoten jedoch nicht mit Eingabesymbolen sondern mit Zustanden beschriftet sind Die Wurzel von r displaystyle rho nbsp ist mit einem Startzustand versehen die restlichen Beschriftungen erfolgen gemass der Ubergangsrelation Akzeptanzverhalten Bearbeiten Ein unendlicher Baum t displaystyle t nbsp wird von einem Buchi Baumautomaten A displaystyle A nbsp akzeptiert genau dann wenn fur einen Lauf r displaystyle rho nbsp von A displaystyle A nbsp auf t displaystyle t nbsp gilt Auf jedem unendlichen Pfad in r displaystyle rho nbsp kommen unendlich viele Endzustande vor Die durch einen Buchi Baumautomaten akzeptierten Baume bilden eine Buchi erkennbare Baumsprache Die Klasse der Buchi erkennbaren Baumsprachen ist unter Vereinigung abgeschlossen Unter Komplement ist sie hingegen nicht abgeschlossen wie sich mit einer Variante des Pumping Lemmas zeigen lasst Jeder Buchi Baumautomat lasst sich in einen aquivalenten Muller Baumautomaten MBA umwandeln Da die Klasse der muller erkennbaren Baumsprachen unter Komplement abgeschlossen ist sind Buchi Baumautomaten schwacher als MBAs und als Paritatsbaumautomaten welche aquivalent zu MBAs sind Co Buchi Automaten BearbeitenEin deterministischer Co Buchi Automat ist ein 5 Tupel A Q S d q 0 F displaystyle A left Q Sigma delta q 0 F right nbsp und unterscheidet sich von einem deterministischen Buchi Automaten nur durch das Akzeptanzverhalten Wahrend ein Buchi Automat ein Wort akzeptiert falls immer wieder ein Endzustand besucht wird so akzeptiert ein Co Buchi Automat ein Wort nur wenn ab einem gewissen Punkt nur noch Endzustande besucht werden Schreibt man dies etwas formaler auf so sieht man dass der Existenzquantor und der Allquantor vertauscht werden Ein unendliches Wort w a 1 a 2 a 3 displaystyle w a 1 a 2 a 3 ldots nbsp wird vom deterministischen Buchi Automaten bzw Co Buchi Automaten A Q S d q 0 F displaystyle A left Q Sigma delta q 0 F right nbsp akzeptiert genau dann wenn fur den zugehorigen eindeutigen Pfad q 0 q 1 q 2 q 3 displaystyle q 0 rightarrow q 1 rightarrow q 2 rightarrow q 3 ldots nbsp gilt i j i displaystyle forall i exists j geq i nbsp mit q j F displaystyle q j in F nbsp Buchi Automat i j i displaystyle exists i forall j geq i nbsp mit q j F displaystyle q j in F nbsp Co Buchi Automat Literatur BearbeitenWolfgang Thomas Automata on Infinite Objects In Jan van Leeuwen Hrsg Handbook of Theoretical Computer Science Band B Formal Models and Semantics Elsevier Science Publishers u a Amsterdam u a 1990 ISBN 0 444 88074 7 S 133 164 Abgerufen von https de wikipedia org w index php title Buchi Automat amp oldid 205277487