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 automatuEdytuj

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

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

  • dla każdego stanu   z   stwórzmy stan   z  
  • dla każdego przejścia   (gdzie   należy do  ) dodajmy przejście  
  • dla każdego przejścia   (gdzie   i   należą do  ) dodajmy przejście  
  • Oznaczmy wszystkie stany z   jako akceptowalne.

Jeśli automat ten wejdzie w dowolny stan z   to nigdy tego zbioru nie opuści, czyli w szczególności nigdy nie wejdzie w stan z   – 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   Weźmy dowolne przejście po tym miejscu i zmieńmy je na przejście z   do   i „poprimujmy” wszystkie następne przejścia. Automat ten będzie więc w   nieskończenie często, czyli zaakceptuje słowo.

Algorytm budowania alternatywy automatówEdytuj

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   gdzie   jest stanem pierwszego automatu,   zaś stanem drugiego, relacją przejść jest natomiast zbiór   takich że   w pierwszym automacie,   zaś w drugim.

Zbiór stanów akceptujących składa się z tych stanów   gdzie albo   jest akceptujący w pierwszym automacie, albo   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   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ówEdytuj

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   gdzie   i   to stany automatów składowych,   zaś to liczba od 0 do 2, taka że:

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

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   lub z  

PrzykładEdytuj

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

 
 
 
 

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