Presentazione di PowerPoint

Automi e stringhe
Lezione n°24
Prof.ssa Rossella Petreschi
Lezione del 9 /01/ 2013 del
Corso di Algoritmi e Strutture Dati
Riferimenti:
Capitolo 32 del testo Cormen,Leiserson,Rivest, Stein
“Introduzione agli algoritmi”
Edizioni: Jackson libri
Automi a stati finiti
Un automa a stati finiti è una quintupla (Q,q0,A, S,) dove
•
Q è un insieme finito di stati.
•
q0 in Q è lo stato iniziale.
•
A in Q è un insieme distinguibile di stati accettanti.

 è un alfabeto di input finito.

 è una funzione da Qx in Q, chiamata funzione di transizione di M, ovvero
(q,a) è il nuovo stato in cui giunge l’automa che era nello stato q dopo aver letto
il carattere a.
Se lo stato corrente q appartiene ad A, si dice che la macchina M accetta la stringa
appena letta, altrimenti l’input letto è rifiutato. Si dice che una macchina accetta una
stringa w sess (w) appartiene ad A e la funzione  da * a Q si chiama
funzione stato finale ed è definita ricorsivamente:
() =q0 ; (wa) =((w),a), per w in * e a in 
Automi di corrispondenza fra stringhe
Per un automa di corrispondenza fra stringhe relativo ad un dato pattern
P [1,…,m] si ha
•
Q , l’insieme finito di stati, è (0,1,…m).
•
lo stato iniziale q0 in Q è 0.
•
l’unico stato accettante di A in Q è m.

 è un alfabeto di input finito.

 , funzione di transizione da Qx in Q, è così definita
(q,a) = s(Pqa), per ogni q in Q e a in 
Con s(Pqa), corrispondenza tra * e (0,1,…m), che misura il più lungo prefisso
del pattern P che è anche suffisso di Pqa
sè chiamata funzione suffisso
Idea di base
In ogni stato q l’automa ha bisogno solo di conoscere la lunghezza del più lungo
prefisso di P che sia suffisso di quanto letto fino a quel momento.
Per la funzione suffisso si ha che:
- Per un qualunque carattere a e una qualunque stringa x, vale s(xa) ≤ s(x)+1
- Per un qualunque carattere a e una qualunque stringa x, se q = s(x),
vale s(xa) ≤ s(Pqa)
Calcolo di 
ciclo da m
ciclo da 
al più m-1
fino ad m confronti
Tempo O(m3 )
Algoritmo calcola (P, )
m=lungh(P);
for q=0 to m
do for ogni a in 
do k = min (m+1,q+2)
repeat k = k-1 until Pk suff Pqa
(q,a) = k
ritorna 
Algoritmo stringhe/automi
Algoritmo stringhe/automi (T,,m)
n=lungh(T); q=0;
for i=1 to n do
q = (q, T(i))
if q=m then s = i-m; write “il pattern appare con spostamento s”
Tempo O(n) + calcolo di 
Il miglior algoritmo di corrispondenza fra stringhe e automi richiede tempo O (n+m)
Correttezza dell’algoritmo stringhe/automi
TEOREMA:
Se è la funzione stato-finale di un automa di corrispondenza tra stringhe per un dato
pattern P(1,…,m) e T(1,n) è un testo di input per l’automa, allora (Ti)=s(Ti), i=0,…,n
Dimostrazione
Si procede per induzione
Passo base T0 =  quindi  (T0) = s(T0) = 0
Ipotesi induttiva (Ti) = s(Ti)
Si prova che (Ti+1) = s(Ti+1)
(Ti+1) = (Tia) = ((Ti),a) = (q,a) = s(Pq,a) = s(Ti,a)  s(Ti+1)