[AUTOMI]Probabilità di accettazione di un PDA

[gabry451]

Salve,
ho costruito il seguente pda che data una parola w#x verifica che x contenga come sottostringa il reverse di W. W e X € {0,1}

EDIT:





Qualcuno mi potrebbe spiegare come posso calcolare la probabilità di accettazione di una stringa da questo PDA?
Ho provato a cercare in internet ma non ho trovato nulla

[gabry451]

Dimenticavo che il simbolo "$" lo ho usato come notazione per identificare la fine dello stack.

[hamming_burst]

Ciao,
ma in un corso di Linguaggi ed Automi avete trattato gli automi probabilistici? Oppure è solo un esercizio fuori contesto?
Cmq mi pare si deve ricorrere alle nozioni delle catene di Markov discrete o simili.

[gabry451]

Si ma è nella normalità, penso che NFA e PDA vengano trattati da tutte le università.
Ho visto che il professore della mia università calcolava la probabilità di accettazione di una stringa, ma non ho mai sentito delle catene di Markov.
Comunque io sono arrivato a questa soluzione, che non so quanto sia corretta

Abbiamo un evento che si verifica quando un 1(nella pila) 1(nell' input) oppure quando abbiamo 0(nella pila) e (0 nell' input) dopo che è stato consumato l' input #:

Se questo evento avviene k volte abbiamo k-1 opzione binarie, dopo abbiamo (k-1)+1 opzioni.

La probabilità Sarà 1/(2^k)

Se abbiamo più occorrenze di w all' interno di x allora dobbiamo sommare le diverse probabilità per ogni n occorrenza.

Per esempio nella stringa:

111#010111000110111 k1=2 k2=7

quindi 1/(2^7)+1/(2^2)= 0,257



Comunque il pda che ho postato era una prima versione e non è corretto perchè il linguaggio sta in {0,1}* e quindi anche la stringa vuota e la stringa composta da solo # deve essere accettata. Aggiorno ora il disegno