Automat Büchiego

Ten artykuł od 2016-01 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle X}$ jest zbiorem stanów akceptowalnych, a ${\displaystyle Y}$ jest zbiorem stanów nieakceptowalnych danego języka, to stwórzmy zbiór stanów ${\displaystyle Y',}$ taki że:

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

Jeśli automat ten wejdzie w dowolny stan z ${\displaystyle Y',}$ to nigdy tego zbioru nie opuści, czyli w szczególności nigdy nie wejdzie w stan z ${\displaystyle 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 ${\displaystyle Y.}$ Weźmy dowolne przejście po tym miejscu i zmieńmy je na przejście z ${\displaystyle Y}$ do ${\displaystyle Y',}$ i „poprimujmy” wszystkie następne przejścia. Automat ten będzie więc w ${\displaystyle 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 ${\displaystyle (A,B),}$ gdzie ${\displaystyle A}$ jest stanem pierwszego automatu, ${\displaystyle B}$ zaś stanem drugiego, relacją przejść jest natomiast zbiór ${\displaystyle (A,B)\to ^{a}(C,D),}$ takich że ${\displaystyle A\to ^{a}C}$ w pierwszym automacie, ${\displaystyle B\to ^{a}D}$ zaś w drugim.

Zbiór stanów akceptujących składa się z tych stanów ${\displaystyle (A,B),}$ gdzie albo ${\displaystyle A}$ jest akceptujący w pierwszym automacie, albo ${\displaystyle 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 ${\displaystyle (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 ${\displaystyle (A,B,X),}$ gdzie ${\displaystyle A}$ i ${\displaystyle B}$ to stany automatów składowych, ${\displaystyle X}$ zaś to liczba od 0 do 2, taka że:

• Jeśli ${\displaystyle X=0}$ i ${\displaystyle A}$ jest akceptujący, zmień ${\displaystyle X}$ na 1.
• Jeśli ${\displaystyle X=1}$ i ${\displaystyle B}$ jest akceptujący, zmień ${\displaystyle X}$ na 2.
• Stany z ${\displaystyle X=2}$ są akceptujące. Jeśli ${\displaystyle X=2,}$ zmień ${\displaystyle X}$ na 0.
• W przeciwnym wypadku nie zmieniaj ${\displaystyle 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 ${\displaystyle X=0}$ lub z ${\displaystyle 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 ${\displaystyle A}$ i ${\displaystyle B,}$ przy czym ${\displaystyle A}$ jest startowy, ${\displaystyle B}$ jest akceptujący, a przejścia to (1 odwraca stan, 0 zachowuje):

${\displaystyle A\to ^{0}A,}$

${\displaystyle A\to ^{1}B,}$

${\displaystyle B\to ^{0}B,}$

${\displaystyle 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 ${\displaystyle A}$ na ${\displaystyle 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.