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.

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 ${\displaystyle \Sigma }$ è una sestupla ${\displaystyle {\mathcal {A}}=\left\langle \Sigma ,Q,\delta ,s_{0},T.\pi \right\rangle }$^[4] con:

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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 ${\displaystyle \lambda P(a)P(b)=(0,0,{\tfrac {3}{8}},{\tfrac {5}{8}})}$, con la probabilità di accettare ${\displaystyle ab}$ che è pertanto ${\displaystyle \lambda P(a)P(b)\gamma =3/8}$ .

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

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

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

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

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

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.

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

${\displaystyle \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 ${\displaystyle w=b_{1}b_{2}\cdots b_{n}}$, il coefficiente ${\displaystyle P(w)_{1,2}}$ della matrice ${\displaystyle P(w)}$ è uguale a

${\displaystyle 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 ${\displaystyle 0,b_{n}b_{n-1}\cdots b_{1}}$. Per un valore di ${\displaystyle \eta }$, il linguaggio ${\displaystyle L({\mathcal {A}},\eta )}$ accettato da questo automa è quindi l'insieme di parole che rappresentano un numero binario maggiore di ${\displaystyle \eta }$. È chiaro che se ${\displaystyle \eta <\eta '}$, allora ${\displaystyle L({\mathcal {A}},\eta )\subset L({\mathcal {A}},\eta ')}$ e questa inclusione è rigorosa. Di conseguenza, esiste un numero non numerabile di linguaggi della forma ${\displaystyle 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.

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${\displaystyle \Omega ({\mathcal {A}})=\{\pi _{\mathcal {A}}(w)\mid w\in A^{*}\}}$.

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

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

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

• 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.

• Modello di Markov nascosto
• Automa a stati finiti
• Algoritmo di Viterbi
• Programmazione dinamica
• Bioinformatica
• Riconoscimento vocale automatico