Automat probabilistyczny

W matematyce i informatyce automat probabilistyczny ( PA ) jest uogólnieniem niedeterministycznego automatu skończonego ; zawiera prawdopodobieństwo danego przejścia do funkcji przejścia , przekształcając ją w macierz przejścia . W ten sposób automat probabilistyczny uogólnia również pojęcia łańcucha Markowa i przesunięcia podrzędnego typu skończonego . Języki probabilistyczne to tzw języki stochastyczne ; obejmują one języki regularne jako podzbiór. Liczba języków stochastycznych jest niezliczona .

Koncepcja została wprowadzona przez Michaela O. Rabina w 1963 roku; pewien szczególny przypadek jest czasami nazywany automatem Rabina (nie mylić z podklasą automatów ω, zwaną również automatami Rabina). W ostatnich latach sformułowano wariant w kategoriach prawdopodobieństw kwantowych, kwantowy automat skończony .

Nieformalny opis

Dla danego stanu początkowego i znaku wejściowego deterministyczny automat skończony (DFA) ma dokładnie jeden następny stan, a niedeterministyczny automat skończony (NFA) ma zbiór następnych stanów. Zamiast tego automat probabilistyczny (PA) ma ważony zbiór (lub wektor ) następnych stanów, w których wagi muszą sumować się do 1 i dlatego można je interpretować jako prawdopodobieństwa (co czyni go wektorem stochastycznym ). Stany pojęć i akceptacja muszą również zostać zmodyfikowane, aby odzwierciedlić wprowadzenie tych wag. Stan maszyny jako dany krok musi teraz być również reprezentowany przez stochastyczny wektor stanów, a stan zaakceptowany, jeśli jego całkowite prawdopodobieństwo znalezienia się w stanie akceptacji przekracza pewną granicę.

PA jest w pewnym sensie krokiem w połowie drogi od deterministycznego do niedeterministycznego, ponieważ pozwala na zestaw kolejnych stanów, ale z ograniczeniami co do ich wagi. Jest to jednak nieco mylące, ponieważ PA wykorzystuje pojęcie liczb rzeczywistych do określenia wag, czego nie ma w definicji zarówno DFA, jak i NFA. Ta dodatkowa swoboda umożliwia im decydowanie o językach, które nie są regularne, takich jak języki p-adyczne z irracjonalnymi parametrami. Jako takie, PA są potężniejsze niż zarówno DFA, jak i NFA (które są równie potężne).

Definicja formalna

Automat probabilistyczny można zdefiniować jako rozszerzenie niedeterministycznego automatu skończonego wraz z dwoma prawdopodobieństwami ${\ Displaystyle (Q, \ Sigma, \ delta, q_ {0}, F)}$ : prawdopodobieństwo $zajścia$ określonej zmiany stanu i zastąpieniu stanu początkowego $dający$ wektor stochastyczny , że automat będzie w danym stanie początkowym.

Dla zwykłego niedeterministycznego automatu skończonego tak

• skończony zbiór stanów ${\ displaystyle Q}$
• skończony zestaw symboli wejściowych ${\ displaystyle \ Sigma}$
• funkcja przejścia ${\ Displaystyle \ delta: Q \ razy \ Sigma \ do \ wp (Q)}$
• zbiór stanów wyróżnionych jako akceptujące (lub $subseteq Q}$ ⊆ Q { $\$ .

Tutaj $)}$$Q$ oznacza zestaw mocy .

Używając curry , funkcję przejścia niedeterministycznego automatu skończonego można zapisać jako członkostwo δ $\ Displaystyle \ delta: Q \ razy \ Sigma \ do \ wp (Q)}$ funkcjonować

${\ Displaystyle \ delta: Q \ razy \ Sigma \ razy Q \ do \ {0,1 \}}$

$\ Displaystyle \ delta (q, a, q ^ {\ pierwsza}) = 1}$${\ Displaystyle q ^ {\ prime } \ in \ delta (q, a)}$ jeśli δ i ${\ displaystyle 0}$ inaczej. Funkcję przejścia curry można rozumieć jako macierz z wpisami macierzy

${\ Displaystyle \ lewo [\ teta _ {a} \ prawo] _ {qq ^ {\ pierwsza}} = \ delta (q, a, q ^{\pierwsza})}$

θ ${\ displaystyle \ theta _ {a}} jest zatem macierzą kwadratową, której wpisy$ zero lub jeden, wskazując, czy przejście ${\ displaystyle q {\ stackrel {a} {\ rightarrow} }q^{\prime }}$ jest dozwolone przez NFA. Taka macierz przejść jest zawsze zdefiniowana dla niedeterministycznego automatu skończonego.

Automat probabilistyczny zastępuje te macierze rodziną prawych macierzy stochastycznych dla każdego symbolu $}$ w alfabecie, tak że prawdopodobieństwo przejścia jest podane przez P za ${\ displaystyle P_ {$

${\ Displaystyle \ lewo [P_ {a} \ prawo] _ {qq ^ {\ pierwsza}}}$

Zmiana stanu z jakiegoś stanu na dowolny musi oczywiście nastąpić z prawdopodobieństwem jeden, i tak musi być

${\ Displaystyle \ suma _ {q ^ {\ liczba pierwsza}} \ lewo [P_ {a} \ prawo] _ {qq ^ {\ liczba pierwsza}} = 1}$

dla wszystkich liter wejściowych $q$ stanów wewnętrznych $\ displaystyle q}$ . Stan początkowy automatu probabilistycznego jest określony przez $displaystyle$ wierszowy , którego składnikami są prawdopodobieństwa poszczególnych stanów początkowych $v}$ które sumują się do 1: v {\

${\ Displaystyle \ suma _ {q} \ lewo [v \ prawo] _ {q} = 1}$

Macierz przejść działa po prawej stronie, tak że stan automatu probabilistycznego po zużyciu ciągu wejściowego byłby następujący ${\ displaystyle abc}$

${\ Displaystyle vP_ {a} P_ {b} P_ {c}}$

W szczególności stan automatu probabilistycznego jest zawsze wektorem stochastycznym, ponieważ iloczyn dowolnych dwóch macierzy stochastycznych jest macierzą stochastyczną, a iloczyn wektora stochastycznego i macierzy stochastycznej jest znowu wektorem stochastycznym. Ten wektor jest czasami nazywany rozkładem stanów , podkreślając, że jest to dyskretny rozkład prawdopodobieństwa .

Formalnie definicja automatu probabilistycznego nie wymaga mechaniki automatu niedeterministycznego, z której można zrezygnować. Formalnie probabilistyczny automat PA jest definiowany jako krotka ${\ Displaystyle (Q, \ Sigma, P, v, F)}$ . Automat Rabina to taki, dla którego początkowy $współrzędnych$ jest wektorem ; to znaczy ma zero dla wszystkich wpisów oprócz jednego, a pozostały wpis to jeden.

Języki stochastyczne

Zbiór języków rozpoznawanych przez automaty probabilistyczne nazywa się językami stochastycznymi . Obejmują one języki regularne jako podzbiór.

Niech $akceptujących ” lub$ ” stanów automatu. Przez $displaystyle$ notacji można również rozumieć, że jest to wektor kolumnowy, który jest funkcją przynależności dla $Q_ {\ text {accept}}$ ; to znaczy ma 1 w miejscach odpowiadających elementom w ${\ Displaystyle Q _ {\ tekst {zaakceptować}}}$ , a zero w przeciwnym razie. Wektor ten można skrócić z prawdopodobieństwem stanu wewnętrznego, tworząc skalar . Język rozpoznawany przez określony automat jest wtedy definiowany jako

${\ Displaystyle L _ {\ eta} = \ {s \ w \ Sigma ^ {*} \ vert vP_ {s} Q _ {\ tekst {zaakceptować}}> \ eta \}}$

gdzie jest zbiorem wszystkich ciągów w $alfabecie$ (tak, $gwiazdą$ Kleene ) . Język zależy od wartości punktu $się$ , zwykle przyjmowanego jako mieszczący w zakresie ${\ displaystyle 0 \ leq \ eta <1}$ .

Język nazywa się η -stochastyczny wtedy i tylko wtedy, gdy istnieje jakiś PA, który rozpoznaje język, na stałe ${\ displaystyle \ eta}$ . Język nazywa się $dla$$-stochastyczny$ i , gdy istnieje jakiś którego η

Mówi się, że punkt odcięcia jest odosobnionym punktem odcięcia wtedy i tylko wtedy, gdy istnieje taki, że δ $\ displaystyle \ delta > 0}$

${\ Displaystyle \ vert vP (s) Q _ {\ tekst {akceptować}} - \ eta \ vert \ geq \ delta}$

dla wszystkich ${\ Displaystyle s \ w \ Sigma ^ {*}}$

Nieruchomości

Każdy język regularny jest stochastyczny, a co ważniejsze, każdy język regularny jest η -stochastyczny. Słabą odwrotnością jest to, że każdy język 0-stochastyczny jest regularny; jednak ogólna odwrotność nie zachodzi: istnieją języki stochastyczne, które nie są regularne.

Każdy $stochastyczny$ η jest dla

Każdy język stochastyczny jest reprezentowany przez automat Rabina.

Jeśli jest izolowanym punktem przecięcia $,$$jest$ językiem

języki p -adyczne

Języki p -adyczne dostarczają przykładu języka stochastycznego, który nie jest regularny, a także pokazują, że liczba języków stochastycznych jest niepoliczalna. Język p -adic jest zdefiniowany jako zbiór ciągów znaków

${\ Displaystyle L _ {\ eta} (p) = \ {n_ {1} n_ {2} n_ {3} \ ldots \ vert 0 \ leq n_{k}<p{\text{i }}0.n_{1}n_{2}n_{3}\ldots >\eta \}}$

literami ${\ Displaystyle 0,1,2, \ ldots, (p-1)}$ .

Oznacza to, że p -adic język jest po prostu zbiorem liczb rzeczywistych w [0, 1], zapisanych w base- p , tak że są one większe niż ${\ displaystyle \ eta}$ . Łatwo jest pokazać, że wszystkie języki p -adyczne są stochastyczne. W szczególności oznacza to, że liczba języków stochastycznych jest niepoliczalna. Język p -adic jest regularny wtedy i tylko wtedy, gdy $racjonalny$ .

Uogólnienia

Automat probabilistyczny ma interpretację geometryczną: wektor stanu można rozumieć jako punkt, który znajduje się na powierzchni standardowego simpleksu , naprzeciw kąta ortogonalnego. Macierze przejścia tworzą monoid , działając na punkt. Można to uogólnić, mając punkt z jakiejś ogólnej przestrzeni topologicznej , podczas gdy macierze przejścia są wybierane ze zbioru operatorów działających w przestrzeni topologicznej, tworząc w ten sposób półautomat . Gdy punkt przecięcia jest odpowiednio uogólniony, mamy automat topologiczny .

Przykładem takiego uogólnienia jest kwantowy automat skończony ; tutaj stan automatu jest reprezentowany przez punkt w zespolonej przestrzeni rzutowej , podczas gdy macierze przejść są ustalonym zbiorem wybranym z grupy unitarnej . Punkt odcięcia rozumiany jest jako granica maksymalnej wartości kąta kwantowego .

Notatki

• Salomaa, Arto (1969). „Skończone automaty niedeterministyczne i probabilistyczne”. Teoria automatów . Oksford: Pergamon Press .