Büchi-Automat

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

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 unendliche Wörter als auch unendliche Bäume zu erkennen.

Inhaltsverzeichnis

1 Büchi-Automaten zur Worterkennung
2 Büchi-Automaten zur Baumerkennung
- 2.1 Akzeptanzverhalten
3 Literatur

[Bearbeiten] Büchi-Automaten zur Worterkennung

[Bearbeiten] Nichtdeterministischer Büchi-Automat zur Worterkennung

Ein nichtdeterministischer Büchi-Automat (NBA) ist ein 5-Tupel $A=\left(Q,\Sigma,\Delta,I,F\right)$ wobei gilt:

$Q$ ist eine endliche Menge von Zuständen, die Zustandsmenge
$Σ$ ist eine endliche Menge von Symbolen, das Eingabealphabet
$Δ$ ist die Übergangsrelation mit $\Delta \subseteq Q \times \Sigma \times Q$
$I$ ist eine endliche Menge von Zuständen mit $I \subseteq Q$ , die Startzustandsmenge
$F$ ist eine endliche Menge von Zuständen mit $F \subseteq Q$ , die Endzustandsmenge

[Bearbeiten] Deterministischer Büchi-Automat zur Worterkennung

Ein deterministischer Büchi-Automat (DBA) ist ein 5-Tupel $A=\left(Q,\Sigma,\delta,q_0,F\right)$ wobei gilt:

$Q$ ist eine endliche Menge von Zuständen, die Zustandsmenge
$Σ$ ist eine endliche Menge von Symbolen, das Eingabealphabet
$δ$ ist die Übergangsfunktion mit $\delta: Q \times \Sigma \rightarrow Q$
$q 0$ ist der Startzustand mit $q_0 \in Q$
$F$ ist eine endliche Menge von Zuständen mit $F \subseteq Q$ , die Endzustandsmenge

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

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 über $\Sigma^{\omega}=\left\{a,b\right\}^{\omega}$ , der die Sprache $\{w \in \Sigma^\omega \mid w=\Sigma^*b^\omega \}$ erkennt, also die Sprache aller ω-Wörter, die nur endlich viele a enthalten.

Ein nichtdeterministischer Büchi-Automat kann dagegen angeben werden.

[Bearbeiten] Akzeptanzverhalten

Ein unendliches Wort $w=a_1a_2a_3 \ldots$ wird vom (nichtdeterministischen) Büchi-Automaten $A$ akzeptiert genau dann, wenn für den zugehörigen (unendlichen)Pfad $q_0\quad \begin{matrix}a_1 \\ \rightarrow \\ A\end{matrix}\quad q_1 \quad\begin{matrix}a_2 \\ \rightarrow \\ A\end{matrix}\quad q_2\quad \begin{matrix}a_3 \\ \rightarrow \\ A\end{matrix}\quad q_3 \quad\ldots$ gilt

$q_0 \in I$
$(q_i, a_{i+1}, q_{i+1}) \in \Delta$ für alle $i$
es gibt unendlich viele $i$ mit $q_i \in F$

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

Die von einem Büchi-Automaten $A$ akzeptierte ω-Sprache (Menge unendlicher Wörter) ist $L_{\omega}(A)=\{w \in \Sigma^{\omega} \mid w ~ wird ~ von ~ A ~ akzeptiert\}$ .

Diese ω-Sprache heißt dann büchi-erkennbar.

Jede büchi-erkennbare ω-Sprache kann durch $\cup_{i=1}^m U_i V_i^{\omega}$ dargestellt werden, wobei für alle $i$ $U i$ und $V i$ reguläre Sprachen sind. Auf Grund diesen 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.

[Bearbeiten] Büchi-Automaten zur Baumerkennung

Die Abkürzung BBA (engl.: 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 den Ausgangsgrad $k$ hat.

Der Aufbau des Büchi-Automaten zur Baumerkennung entspricht dem des NBA, wobei jedoch die Übergangsrelation eine andere Form hat:

$\Delta \subseteq Q \times \Sigma \times Q^k$ .

Ein Lauf eines Büchi-Baumautomaten $A$ auf einem Eingabebaum $t$ ist ein Baum $ρ$ , der die gleichen Eigenschaften wie $t$ 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.

[Bearbeiten] Akzeptanzverhalten

Ein unendlicher Baum $t$ wird von einem Büchi-Baumautomaten $A$ akzeptiert genau dann, wenn für einen Lauf $ρ$ von $A$ auf $t$ 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.