Probabilistisk automat

Inom matematik och datavetenskap är den probabilistiska automaten ( PA ) en generalisering av den icke-deterministiska finita automaten ; den inkluderar sannolikheten för en given övergång till övergångsfunktionen, vilket gör den till en övergångsmatris . Således generaliserar den probabilistiska automaten också begreppen om en Markov-kedja och en subshift av finit typ . De språk som känns igen av probabilistiska automater kallas stokastiska språk ; dessa inkluderar de vanliga språken som en delmängd. Antalet stokastiska språk är oräkneligt .

Konceptet introducerades av Michael O. Rabin 1963; ett visst specialfall är ibland känt som Rabin-automaten (inte att förväxla med underklassen av ω-automater även kallad Rabin-automater). På senare år har en variant formulerats i termer av kvantsannolikheter, den quantum finita automaten .

Informell beskrivning

För ett givet initialtillstånd och inmatningskaraktär har en deterministisk finit automat (DFA) exakt ett nästa tillstånd, och en icke-deterministisk finit automat (NFA) har en uppsättning nästa tillstånd. En probabilistisk automat (PA) har istället en viktad uppsättning (eller vektor ) av nästa tillstånd, där vikterna måste summeras till 1 och därför kan tolkas som sannolikheter (gör det till en stokastisk vektor ). Begreppen tillstånd och acceptans måste också modifieras för att återspegla införandet av dessa vikter. Maskinens tillstånd som ett givet steg måste nu också representeras av en stokastisk vektor av tillstånd, och ett tillstånd accepterat om dess totala sannolikhet att vara i ett acceptanstillstånd överstiger någon cut-off.

En PA är i någon mening ett halvvägs steg från deterministisk till icke-deterministisk, eftersom den tillåter en uppsättning nästa tillstånd men med restriktioner för deras vikter. Detta är dock något missvisande, eftersom PA använder begreppet de reella talen för att definiera vikterna, vilket saknas i definitionen av både DFA och NFA. Denna extra frihet gör det möjligt för dem att bestämma språk som inte är reguljära, såsom de p-adiska språken med irrationella parametrar. Som sådan är PA:er mer kraftfulla än både DFA:er och NFA:er (som känt är lika kraftfulla).

Formell definition

Den probabilistiska automaten kan definieras som en förlängning av en icke-deterministisk finit automat ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)} ,$ tillsammans med två sannolikheter : sannolikheten $P$ för att en viss tillståndsövergång äger rum, och med initialtillståndet $q_{0}$ ersatt av en stokastisk vektor som ger sannolikheten för att automaten är i ett givet initialtillstånd.

För den vanliga icke-deterministiska finita automaten har man

• en ändlig uppsättning tillstånd $Q$
• en ändlig uppsättning ingångssymboler $\Sigma$
• en övergångsfunktion $\delta :Q\times \Sigma \to \wp (Q)$
• en uppsättning tillstånd $F$ som särskiljs som accepterande (eller slutliga ) tillstånd $F\subseteq Q$ .

Här betecknar $\wp (Q)$ effektuppsättningen för $Q$ .

Genom att använda currying kan övergångsfunktionen $\delta :Q\times \Sigma \to \wp (Q)$ för en icke-deterministisk finit automat skrivas som ett medlemskap fungera

$\delta :Q\times \Sigma \times Q\to \{0,1\}$

så att $\delta (q,a,q^{\prime })=1$ om $q^{\ primtal }\in \delta (q,a)$ och $0$ annars. Funktionen curryövergång kan förstås som en matris med matrisposter

$\left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q ^{\prime })$

Matrisen $\theta _{a}$ är då en kvadratisk matris, vars poster är noll eller ett, som indikerar om en övergång $q{\stackrel {a}{\rightarrow } }q^{\prime }$ är tillåtet av NFA. En sådan övergångsmatris definieras alltid för en icke-deterministisk finit automat.

Den probabilistiska automaten ersätter dessa matriser med en familj av högra stokastiska matriser $P_{a}$ , för varje symbol a i alfabetet $\Sigma$ så att sannolikheten för en övergång ges av

$\left[P_{a}\right]_{qq^{\prime }}$

En tillståndsändring från något tillstånd till vilket tillstånd som helst måste naturligtvis ske med en sannolikhet, och så måste man ha

$\sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1$

för alla inmatade bokstäver $a$ och interna tillstånd $q$ . Det initiala tillståndet för en probabilistisk automat ges av en radvektor $v$ , vars komponenter är sannolikheterna för de individuella initialtillstånden ${\displaystyle q} ,$ som adderas till 1:

$\sum _{q}\left[v\right]_{q}=1$

Övergångsmatrisen verkar till höger, så att tillståndet för den probabilistiska automaten, efter att ha konsumerat inmatningssträngen $abc$ , skulle vara

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

I synnerhet är tillståndet för en probabilistisk automat alltid en stokastisk vektor, eftersom produkten av två godtyckliga stokastiska matriser är en stokastisk matris, och produkten av en stokastisk vektor och en stokastisk matris återigen är en stokastisk vektor. Denna vektor kallas ibland fördelningen av tillstånd , vilket betonar att det är en diskret sannolikhetsfördelning .

Formellt kräver definitionen av en probabilistisk automat inte mekaniken hos den icke-deterministiska automaten, vilket kan undvaras. Formellt definieras en probabilistisk automat PA som tupeln $(Q,\Sigma ,P,v,F)$ . En Rabin-automat är en för vilken den initiala fördelningen $v$ är en koordinatvektor ; det vill säga har noll för alla poster utom en, och den återstående posten är en.

Stokastiska språk

Uppsättningen språk som känns igen av probabilistiska automater kallas stokastiska språk . De inkluderar de vanliga språken som en delmängd.

Låt $F=Q_{\text{acceptera}}\subseteq Q$ vara uppsättningen av "accepterande" eller "slutliga" tillstånd för automaten. Genom missbruk av notation $Q_{\text{acceptera}}$ också förstås som kolumnvektorn som är medlemskapsfunktionen för $Q_{\text{acceptera}}$ ; det vill säga den har en 1 på de platser som motsvarar element i $Q_{\text{acceptera}}$ och en nolla annars. Denna vektor kan kontraheras med sannolikheten för det interna tillståndet för att bilda en skalär . Språket som känns igen av en specifik automat definieras då som

$L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{acceptera}}>\eta \}$

där $\Sigma ^{*}$ är mängden av alla strängar i alfabetet $\Sigma$ (så att * är Kleene-stjärnan ). Språket beror på värdet på skärpunkten $\eta$ , normalt sett inom intervallet $0\leq \eta <1$ .

Ett språk kallas η -stokastiskt om och endast om det finns någon PA som känner igen språket, för fast $\eta$ . Ett språk kallas stokastiskt om och endast om det finns någon $0\leq \eta <1$ för vilken $L_{\eta }$ är η -stokastisk.

En cut-point sägs vara en isolerad cut-point om och endast om det finns en $\delta >0$ så att

$\vert vP(s)Q_{\text{acceptera}}-\eta \vert \geq \delta$

för alla $s\in \Sigma ^{*}$

Egenskaper

Varje reguljärt språk är stokastiskt, och ännu starkare, varje reguljärt språk är η -stokastiskt. En svag motsats är att varje 0-stokastiskt språk är regelbundet; det allmänna motsatsen gäller dock inte: det finns stokastiska språk som inte är regelbundna.

Varje η -stokastiskt språk är stokastiskt, för vissa $0<\eta <1$ .

Varje stokastiskt språk kan representeras av en Rabin-automat.

Om $\eta$ är en isolerad cut-point, så är $L_{\eta }$ ett vanligt språk.

p -adiska språk

De p -adiska språken ger ett exempel på ett stokastiskt språk som inte är regelbundet, och visar också att antalet stokastiska språk är oräkneligt. Ett p -adiskt språk definieras som en uppsättning strängar

$L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\ leq n_{k}<p{\text{ och }}0.n_{1}n_{2}n_{3}\ldots >\eta \}$

i bokstäverna $0,1,2,\ldots ,(p-1)$ .

Det vill säga, ett p -adiskt språk är bara mängden reella tal i [0, 1], skrivna i bas- p , så att de är större än $\eta$ . Det är enkelt att visa att alla p -adiska språk är stokastiska. I synnerhet innebär detta att antalet stokastiska språk är oräkneligt. Ett p -adiskt språk är regelbundet om och endast om $\eta$ är rationell.

Generaliseringar

Den probabilistiska automaten har en geometrisk tolkning: tillståndsvektorn kan förstås vara en punkt som lever på framsidan av standardsimplexet, mitt emot det ortogonala hörnet. Övergångsmatriserna bildar en monoid , som verkar på punkten. Detta kan generaliseras genom att peka kommer från något allmänt topologiskt utrymme , medan övergångsmatriserna väljs från en samling operatörer som verkar på det topologiska utrymmet, vilket bildar en halvautomat . När cut-pointen är lämpligt generaliserad har man en topologisk automat .

Ett exempel på en sådan generalisering är den ändliga kvantautomaten ; här representeras automattillståndet av en punkt i komplext projektivt utrymme , medan övergångsmatriserna är en fast uppsättning vald från den enhetliga gruppen . Skärpunkten förstås som en gräns för det maximala värdet för kvantvinkeln .

Anteckningar

• Salomaa, Arto (1969). "Finita icke-deterministiska och probabilistiska automater". Teori om automater . Oxford: Pergamon Press .