Automat Büchiego

Z Wikipedii

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.

Spis treści

1 Algorytm budowania dopełniania automatu
2 Algorytm budowania alternatywy automatów
3 Algorytm budowania przecięcia automatów
4 Przykład

[edytuj] Algorytm budowania dopełniania automatu

Ponizszy algorytm nie jest poprawny dla dowolnych niedeterministycznych automatow Buchiego. Poprawne konstrukcje, np. Safry, sa 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 $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.

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

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

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

Kategoria: Teoria automatów

We provide Linux to the World

Automat Büchiego

Z Wikipedii

Spis treści

[edytuj] Algorytm budowania dopełniania automatu

[edytuj] Algorytm budowania alternatywy automatów

[edytuj] Algorytm budowania przecięcia automatów

[edytuj] Przykład

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach