Automa a stati finiti probabilistico
# 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. 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$ 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. 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. 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]$.
