Automat Büchiego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

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

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 , taki że:

  • dla każdego stanu z Y stwórzmy stan z
  • dla każdego przejścia (gdzie B należy do Y) dodajmy przejście
  • dla każdego przejścia (gdzie A i B należą do Y) 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 po-primujmy wszystkie następne przejścia. Automat ten będzie więc w nieskończenie często, czyli zaakceptuje słowo.

Algorytm budowania alternatywy automatów[edytuj]

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ów[edytuj]

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 więc zakłada budowanie trójek , gdzie i to stany automatów składowych, 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[edytuj]

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):

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 ilość