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

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.

Fahrer / Team für die Suche eingeben: