Automa a stati finiti probabilistico

Un automa a stati finiti probabilistico è, in matematica e informatica teorica, una generalizzazione degli automi finiti non deterministici dove ogni ad transizione dell'automa è associata una probabilità. Le transizioni sono rappresentate in modo compatto da matrici stocastiche. I linguaggi riconosciuti dagli automi probabilistici sono chiamati linguaggi stocastici; comprendono ed estendono la famiglia dei linguaggi regolari. In particolare, il numero dei linguaggi stocastici non è numerabile; mentre quello dei linguaggi regolari lo è.

Il concetto di automa probabilistico è stato introdotto da Michael O. Rabin nel 1963^[1]^[2]^[3]. Un'estensione di questa definizione porta agli automi quantistici.

Definizione

Un automa probabilistico è fatto da un automa finito non deterministico, dove a ogni transizione è associata una probabilità, ossia un numero reale compreso tra 0 e 1.

Come per un normale automa a stati finiti (non deterministico), un automa probabilistico su un alfabeto $\Sigma$ è una sestupla ${\mathcal {A}}=\left\langle \Sigma ,Q,\delta ,s_{0},T.\pi \right\rangle$ ^[4] con:

$\Sigma =\{a_{0},a_{1},\ldots ,a_{n}\}$ insieme finito di simboli chiamato alfabeto
$Q=\{s_{0},s_{1},\ldots ,s_{m}\}$ insieme finito di stati
$\delta :Q\times \Sigma \to Q$ funzione di transizione fra stati
$s_{0}\in Q$ stato iniziale
$T\subseteq Q$ insieme di stati terminali o finali
$\pi :Q\times \Sigma \to [0,1]^{m+1}$ probabilità di transizione

Il vettore $\pi (s,a)$ , detto "probabilità della transizione", è associato a ogni transizione $(p,a)$ definita da $\delta$ , con $s\in Q{\text{ e }}a\in \Sigma$ . $\pi (s,a)$ assume valori reali positivi fra 0 e 1 tali che il suo i+1-esimo elemento $p_{i}(s,a)$ corrisponde alla probabilità di avere $\delta (s,a)=s_{i}$ , ossia di andare a finire in $s_{i}$ dopo aver letto $a$ in $s$ .

La somma delle probabilità è uguale a 1. Ponendo $p_{i}(s,a)=0$ se $(s,a)$ non ha una transizione in $s_{i}$ , questa condizione si esprime, per ogni stato $s$ e ogni lettera $a$ :

\sum _{i}p_{i}(s,a)=1

Si definiscono delle matrici stocastiche $P(a)$ per ogni lettera $a\in \Sigma$ , tali che

P(a)_{s,i}=p_{i}(s,a)

La funzione $\pi$ si estende alle parole^[4]. Sia $w$ una parola e sia $s_{j}\xrightarrow {w} s_{i}$ un cammino da $s_{j}$ a $s_{i}$ con l'etichetta $w$ . La probabilità di questo cammino è il prodotto delle probabilità delle transizioni che lo compongono. La probabilità $p_{i}(s_{j},w)$ è definita come la somma delle probabilità dei cammini $s_{j}\xrightarrow {w} s_{i}$ da $s_{j}$ a $s_{i}$ con l'etichetta $w$ . Questa definizione si esprime matricialmente con la matrice $Q\times Q$ , prodotto delle matrici $P(a_{1}),P(a_{2}),\ldots ,P(a_{n})$ :

P(w)=P(a_{1})P(a_{2})\cdots P(a_{n})

con $w=a_{1}a_{2}\cdots a_{n}$ . Quindi si ha $P(w)_{s_{j},s_{i}}=p_{i}(s_{j},w)$ .

La "probabilità di accettazione" di una parola $w$ da parte dell'automa probabilistico ${\mathcal {A}}$ è la somma sugli stati terminali $t_{i}\in T$ delle probabilità $\pi (s_{0},w)$ , dove $s_{0}$ è lo stato iniziale. Questa probabilità si scrive anche $\pi _{\mathcal {A}}(w)$ . Anche questo valore si può esprimere in forma matriciale:

\pi _{\mathcal {A}}(w)=\lambda P(w)\gamma

dove $\lambda$ è il $Q$ -vettore linea i cui valori sono tutti zero tranne quello di indice $i$ , che vale 1, e dove $\gamma$ è il $Q$ -vettore colonna con i valori tutti zero eccetto quelli il cui indice è in $T$ , che valgono 1.

Esempio

Prendiamo l'esempio a destra di un automa a quattro stati, le matrici $P(a)$ e $P(b)$ e vettori $\lambda$ e $\gamma$ sono dati da:

\lambda =(1,0,0,0)\qquad P(a)={\begin{pmatrix}0&{\tfrac {3}{4}}&{\tfrac {1}{4}}&0\\0&1&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&0\\0&0&0&1\end{pmatrix}}\qquad P(b)={\begin{pmatrix}1&0&0&0\\0&0&{\tfrac {1}{2}}&{\tfrac {1}{2}}\\0&0&0&1\\0&0&0&1\end{pmatrix}}\qquad \gamma ={\begin{pmatrix}0\\0\\1\\0\end{pmatrix}}

Ad esempio, abbiamo $\lambda P(a)P(b)=(0,0,{\tfrac {3}{8}},{\tfrac {5}{8}})$ , con la probabilità di accettare $ab$ che è pertanto $\lambda P(a)P(b)\gamma =3/8$ .

Linguaggio stocastico

Soglia di accettazione

Sia $\eta$ un numero reale tale che $0\leq \eta <1$ . Il linguaggio accettato dall'automa probabilistico ${\mathcal {A}}$ con soglia $\eta$ è l'insieme delle parole la cui probabilità di accettazione è maggiore di $\eta$ . Questo linguaggio stocastico è $L({\mathcal {A}},\eta )$ , definito da

L({\mathcal {A}},\eta )=\{w\in A^{*}\mid \lambda P(w)\gamma >\eta \}

Il numero $\eta$ è chiamato "soglia" o cut point.

Un cut point è detto "isolato" se esiste un numero reale $\delta >0$ tale che, per ogni parola $w$ , si ha

\left|\pi _{\mathcal {A}}(w)-\eta \right|\geq \delta

Proprietà

Tutti i linguaggi regolari sono stocastici e alcune restrizioni dei linguaggi stocastici sono regolari:

Ogni linguaggio stocastico la cui soglia è 0 è razionale.
Ogni linguaggio stocastico isolato è razionale.

Di contro, non vi è l'uguaglianza, come mostra l'esempio seguente.

Esempio di un linguaggio stocastico che non è regolare

Sia l'automa ${\mathcal {A}}$ a due stati sull'alfabeto binario dato dalle matrici:

\lambda =(1,0)\qquad P(0)={\begin{pmatrix}1&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}\end{pmatrix}}\qquad P(1)={\begin{pmatrix}{\tfrac {1}{2}}&{\tfrac {1}{2}}\\0&1\end{pmatrix}}\qquad \gamma ={\begin{pmatrix}0\\1\end{pmatrix}}

Per una parola binaria $w=b_{1}b_{2}\cdots b_{n}$ , il coefficiente $P(w)_{1,2}$ della matrice $P(w)$ è uguale a

P(w)_{1,2}=\sum _{j=1}^{n}b_{j}2^{n+1-j}

;

Questo è il numero razionale che si può scrivere in notazione binaria $0,b_{n}b_{n-1}\cdots b_{1}$ . Per un valore di $\eta$ , il linguaggio $L({\mathcal {A}},\eta )$ accettato da questo automa è quindi l'insieme di parole che rappresentano un numero binario maggiore di $\eta$ . È chiaro che se $\eta <\eta '$ , allora $L({\mathcal {A}},\eta )\subset L({\mathcal {A}},\eta ')$ e questa inclusione è rigorosa. Di conseguenza, esiste un numero non numerabile di linguaggi della forma $L({\mathcal {A}},\eta )$ per questo automa; poiché il numero di linguaggi regolari è numerabile, ciò implica l'esistenza di linguaggi stocastici che non sono regolari.

Problemi di decidibilità

La maggior parte dei problemi sono indecidibili^[5]. Questi problemi possono essere formulati anche mediante quella che viene chiamata "immagine" di un automa a stati finiti probabilistico, definito come l'insieme $\Omega ({\mathcal {A}})=\{\pi _{\mathcal {A}}(w)\mid w\in A^{*}\}$ .

Il problema di sapere se il linguaggio $L({\mathcal {A}},\eta )$ accettato è vuoto o no, è indecidibile per $0<\eta <1$ . Equivale al problema di sapere se $\Omega ({\mathcal {A}})$ contiene un valore maggiore di $\eta$ .

Il problema di sapere se un numero $\eta$ è una cut point isolato per un automa ${\mathcal {A}}$ , è indecidibile. Equivale al problema di sapere se c'è un intervallo aperto centrato intorno $\eta$ disgiunto da $\Omega ({\mathcal {A}})$ .

Sapere se esiste un numero $\eta$ che è un cut point isolato per ${\mathcal {A}}$ , è indecidibile. Equivale a sapere se $\Omega ({\mathcal {A}})$ è denso nell'intervallo $[0,1]$ .

Note

^ Rabin.
^ Paz.
^ Arto Salomaa, II, in Theory of Automata, Pergamon Press, 1969.
^ ^a ^b Rabin, p. 234.
^ Vincent Blondel, Vincent Canterini, Undecidable Problems for Probabilistic Automata of Fixed Dimension, in Theory of Computing Systems, vol. 36, 2008.

Bibliografia

Michael O. Rabin, Probabilistic Automata, in Information and Control, vol. 6, 1963, pp. 230-245. URL consultato il 4 settembre 2021.
Azaria Paz, Introduction to probabilistic automata, collana Computer science and applied mathematics, Academic Press, 1971.

Voci correlate

Portale Informatica

Portale Matematica

[1] Rabin.

[2] Paz.

[3] Arto Salomaa, II, in Theory of Automata, Pergamon Press, 1969.

[rab234-4] Rabin, p. 234.

[5] Vincent Blondel, Vincent Canterini, Undecidable Problems for Probabilistic Automata of Fixed Dimension, in Theory of Computing Systems, vol. 36, 2008.

[1]

[2]

[3]

[4]

[5]