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 è una sestupla 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. 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. 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 .

Note

Bibliografia

Voci correlate

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

Categoria:Metodi formali Categoria:Teoria della calcolabilità Categoria:Teoria degli automi