Automat_Büchiego.pdf

Automat Büchiego – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_Büchiego

Automat Büchiego

Z Wikipedii, wolnej encyklopedii

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

Algorytm budowania dopełniania automatu

Ponizszy algorytm nie jest poprawny dla dowolnych

niedeterministycznych automatow Buchiego. Poprawne konstrukcje, np.

Safry, sa znacznie bardziej skomplikowane.

1 z 4

29.05.2011 18:14

Automat Büchiego – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_Büchiego

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 A 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 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 , 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

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

, takich że

w pierwszym

automacie,

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

2 z 4

29.05.2011 18:14

Automat Büchiego – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_Büchiego

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

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

Źródło „http://pl.wikipedia.org/wiki/Automat_B%C3%BCchiego”

Kategoria: Teoria automatów

3 z 4

29.05.2011 18:14

Automat Büchiego – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_Büchiego

Tę stronę ostatnio zmodyﬁkowano 00:47, 3 paź 2010. Tekst udostępniany na

licencji Creative Commons: uznanie autorstwa, na tych samych warunkach,

z możliwością obowiązywania dodatkowych ograniczeń. Zobacz szczegółowe

informacje o warunkach korzystania.

4 z 4

29.05.2011 18:14

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: