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

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ść
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.