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.
Indice
1Definizione
2Esempio
3Linguaggio stocastico
3.1Soglia di accettazione
3.2Proprietà
3.2.1Esempio di un linguaggio stocastico che non è regolare
3.3Problemi di decidibilità
4Note
5Bibliografia
6Voci correlate
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 è una sestupla [4] con:
insieme finito di simboli chiamato alfabeto
insieme finito di stati
funzione di transizione fra stati
stato iniziale
insieme di stati terminali o finali
probabilità di transizione
Il vettore , detto "probabilità della transizione", è associato a ogni transizione definita da , con . assume valori reali positivi fra 0 e 1 tali che il suo i+1-esimo elemento corrisponde alla probabilità di avere , ossia di andare a finire in dopo aver letto in .
La somma delle probabilità è uguale a 1. Ponendo se non ha una transizione in , questa condizione si esprime, per ogni stato e ogni lettera :
Si definiscono delle matrici stocastiche per ogni lettera , tali che
La funzione si estende alle parole[4]. Sia una parola e sia un cammino da a con l'etichetta . La probabilità di questo cammino è il prodotto delle probabilità delle transizioni che lo compongono. La probabilità è definita come la somma delle probabilità dei cammini da a con l'etichetta . Questa definizione si esprime matricialmente con la matrice , prodotto delle matrici :
con . Quindi si ha .
La "probabilità di accettazione" di una parola da parte dell'automa probabilistico è la somma sugli stati terminali delle probabilità , dove è lo stato iniziale. Questa probabilità si scrive anche . Anche questo valore si può esprimere in forma matriciale:
dove è il -vettore linea i cui valori sono tutti zero tranne quello di indice , che vale 1, e dove è il -vettore colonna con i valori tutti zero eccetto quelli il cui indice è in , che valgono 1.
Esempio
Prendiamo l'esempio a destra di un automa a quattro stati, le matrici e e vettori e sono dati da:
Ad esempio, abbiamo , con la probabilità di accettare che è pertanto .
Linguaggio stocastico
Soglia di accettazione
Sia un numero reale tale che . Il linguaggio accettato dall'automa probabilistico con soglia è l'insieme delle parole la cui probabilità di accettazione è maggiore di . Questo linguaggio stocastico è , definito da
Il numero è chiamato "soglia" o cut point.
Un cut point è detto "isolato" se esiste un numero reale tale che, per ogni parola , si ha
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 a due stati sull'alfabeto binario dato dalle matrici:
Per una parola binaria , il coefficiente della matrice è uguale a
;
Questo è il numero razionale che si può scrivere in notazione binaria . Per un valore di , il linguaggio accettato da questo automa è quindi l'insieme di parole che rappresentano un numero binario maggiore di . È chiaro che se , allora e questa inclusione è rigorosa. Di conseguenza, esiste un numero non numerabile di linguaggi della forma 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.
Il problema di sapere se il linguaggio accettato è vuoto o no, è indecidibile per . Equivale al problema di sapere se contiene un valore maggiore di .
Il problema di sapere se un numero è una cut point isolato per un automa , è indecidibile. Equivale al problema di sapere se c'è un intervallo aperto centrato intorno disgiunto da .
Sapere se esiste un numero che è un cut point isolato per , è indecidibile. Equivale a sapere se è denso nell'intervallo .
^ 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.