Automat Büchiego

Automat Büchiego (ang. Büchi automaton) to rozszerzenie automatu skończonego na słowa nieskończone. Automat Büchiego składa się z:

• alfabetu
• zbioru stanów z wyróżnionym stanem startowym oraz podzbiorem stanów akceptujących
• funkcji przejścia, która pobiera aktualny stan oraz literę alfabetu i zwraca nowy stan (deterministyczne automaty Büchiego), lub relacji przejścia, która może zwracać wiele stanów (niedeterministyczne automaty Büchiego)

Słowo (nieskończone) jest akceptowane przez automat Büchiego, jeśli stan akceptujący wystąpi w tym słowie nieskończenie wiele razy.

W przeciwieństwie do zwykłych automatów skończonych, gdzie automaty deterministyczne i niedeterministyczne miały taką samą moc, niedeterministyczne automaty Büchiego są silniejsze od deterministycznych.

Niedeterministyczne automaty Büchiego są zamknięte ze względu na dopełnienie, przecięcie i alternatywę.

Dopełnienie automatu deterministycznego może być automatem niedeterministycznym.

Algorytm budowania dopełniania automatu

Ponizszy algorytm nie jest poprawny dla dowolnych niedeterministycznych automatow Buchiego. Poprawne konstrukcje, np. Safry, sa znacznie bardziej skomplikowane.

Jeśli X jest zbiorem stanów akceptowalnych, a Y jest zbiorem stanów nieakceptowalnych danego języka, to stwórzmy zbiór stanów $Y^\prime$, taki że:

• dla każdego stanu $A$ z Y stwórzmy stan $A^\prime$ z $Y^\prime$
• dla każdego przejścia $A \rightarrow^a B$ (gdzie B należy do Y) dodajmy przejście $A \rightarrow^a B^\prime$
• dla każdego przejścia $A \rightarrow^a B$ (gdzie A i B należą do Y) dodajmy przejście $A^\prime \rightarrow^a B^\prime$
• Oznaczmy wszystkie stany z $Y^\prime$ jako akceptowalne

Jeśli automat ten wejdzie w dowolny stan z $Y^\prime$, to nigdy tego zbioru nie opuści, czyli w szczególności nigdy nie wejdzie w stan z $X$ – a więc zaakceptuje tylko słowa nie należące do oryginalnego języka.

Jeśli jakieś słowo nie jest akceptowane przez automat oryginalny, to od pewnego momentu wszystkie stany należą do $Y$. Weźmy dowolne przejście po tym miejscu i zmieńmy je na przejście z $Y$ do $Y^\prime$, i po-primujmy wszystkie następne przejścia. Automat ten będzie więc w $Y^\prime$ nieskończenie często, czyli zaakceptuje słowo.

Algorytm budowania alternatywy automatów

Alternatywę automatów Büchiego można zbudować tak samo jak alternatywę zwykłych automatów skończonych – za zbiór stanów przyjmujemy zbiór par $(A,B)$, gdzie $A$ jest stanem pierwszego automatu, $B$ zaś stanem drugiego, relacją przejść jest natomiast zbiór $(A,B)\rightarrow^a (C,D)$, takich że $A\rightarrow^a C$ w pierwszym automacie, $B\rightarrow^a D$ zaś w drugim.

Zbiór stanów akceptujących składa się z tych stanów $(A,B)$, gdzie albo $A$ jest akceptujący w pierwszym automacie, albo $B$ w drugim.

Uruchomienie takiego automatu jest równoważne uruchomieniu pary automatów na tym samym słowie, przy czym jeśli jeden z tych automatów akceptuje słowo, to automat alternatywy również je zaakceptuje (będzie miał nieskończenie wiele stanów $(A,B)$, gdzie A lub B są akceptujące). Jeśli zaś żaden z 2 automatów nie zaakceptuje słowa, to automat alternatywy będzie miał skończenie wiele stanów akceptujących, czyli też go nie zaakceptuje.

Algorytm budowania przecięcia automatów

Budowanie przecięcia jest trudniejsze – nie możemy po prostu za stany akceptujące przyjąć pary stanów, które są akceptujące w obu automatach. Być może na przemian występują raz stan akceptujący lewego, a potem stan akceptujący prawego (wyobraźmy sobie np. parę automatów akceptujących słowa jeden z nieskończoną ilośćią 0, a drugi z nieskończoną ilością 1).

Konstrukcja więc zakłada budowanie trójek $(A,B,X)$, gdzie $A$ i $B$ to stany automatów składowych, $X$ zaś to liczba od 0 do 2, taka że:

• Jeśli X = 0, i A jest akceptujący, zmień X na 1
• Jeśli X = 1, i B jest akceptujący, zmień X na 2
• Stany z X=2 są akceptujące. Jeśli X = 2, zmień X na 0
• W przeciwnym wypadku nie zmieniaj X.

Automat taki działa na zasadzie:

• najpierw szukamy w ciągu stanów stanu akceptowanego przez pierwszy automat
• szukamy dalej, aż znajdziemy stan akceptowany przez drugi automat
• ustawiamy na moment stan na akceptujący

Jeśli oba automaty składowe zaakceptują nieskończenie wiele razy, zrobi to też automat przecięcia. Jeśli któryś z nich zaakceptuje co najwyżej skończenie wiele razy, automat przecięcia do końca będzie miał stan z X=0 lub z X=1.

Przykład

Weźmy na przykład alfabet złożony ze znaków 0 i 1. Niech automat Büchiego ma stany A i B, przy czym A jest startowy, B jest akceptujący, a przejścia to (1 odwraca stan, 0 zachowuje):

$A\rightarrow^0 A$

$A\rightarrow^1 B$

$B\rightarrow^0 B$

$B\rightarrow^1 A$

Nieskończone słowa akceptowane przez ten język to te, w których stan B występuje nieskończenie wiele razy, czyli albo 1 występuje nieskończenie wiele razy (słowo nie kończy się samymi zerami), albo w słowie jest skończenie wiele jedynek, ale ostatnia jedynka zmieniła stan automatu z A na B. Czyli język akceptuje słowa w których:

• jedynek jest nieskończenie wiele
• lub jedynek jest nieparzysta ilość

Zmieniając stan startowy z A na B uzyskalibyśmy język słów nieskończonych, w których:

• jedynek jest nieskończenie wiele
• lub jedynek jest parzysta ilość