Automat Büchiego

Niedetermistyczny automat Büchiego który rozpoznaje (0∪1)*0^ω

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

Poniższy algorytm nie jest poprawny dla dowolnych niedeterministycznych automatów Buchiego. Poprawne konstrukcje, np. Safry, są znacznie bardziej skomplikowane.

Jeżeli $X$ jest zbiorem stanów akceptowalnych, a $Y$ jest zbiorem stanów nieakceptowalnych danego języka, to stwórzmy zbiór stanów $Y',$ taki że:

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

Jeśli automat ten wejdzie w dowolny stan z $Y',$ 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 nienależą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',$ i „poprimujmy” wszystkie następne przejścia. Automat ten będzie więc w $Y'$ 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)\to ^{a}(C,D),$ takich że $A\to ^{a}C$ w pierwszym automacie, $B\to ^{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ścią 0, a drugi z nieskończoną ilością 1).

Konstrukcja zakłada więc 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\to ^{0}A,$

$A\to ^{1}B,$

$B\to ^{0}B,$

$B\to ^{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 liczba.

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 liczba.