Automi a stati finiti

• Dare la definizione di funzione di transizione per la ricerca esatta tramite automa a stati finiti specificando in particolare dominio e codominio
• Spiegare come avviene la ricerca esatta di $P$ in $T$ con automa a stati finiti, supponendo di avere già definito la funzione di transizione $\delta$. Specificare in particolar modo come vengono identificate le occorrenze.
• Descrivere l’algoritmo di ricerca esatta di un pattern in un testo tramite automa a stati finiti, cioè descrivere la fase di preprocessing e la fase di scansione del testo specificando come vengono trovate le occorrenze del pattern.
• L’esecuzione della ricerca esatta di $P = abcaac$ in testo $T$ con automa a stati finiti passa dallo stato 4 allo stato 2 dopo aver letto un certo simbolo $\sigma$ di $T$. Specificare, motivando la risposta, che simbolo è $\sigma$.
• Siano $P = ccaca$ e $T=bccacaec$. (1) specificare la funzione di transizione di $P$. (2) mostrare l’ASF per cercare $P$ in $T$, evidenziando gli stati che identificano un’occorrenza di $P$ in $T$, mostrare inoltre il calcolo delle posizioni di inizio di ciascuna occorrenza sulla base dello stato trovato
• Sono dati, per la funzione di transizione per la ricerca di un pattern $P$ in un testo tramite ASF; i seguenti valori (…). Specificare il pattern $P$ e (in forma tabellare) la funzione di transizione completa.

KMP

• L’esecuzione della ricerca esatta di $P = bbbbbacca$ in un testo $T$ con l’algoritmo KMP si trova con la finestra $W$ in posizione 32. Il più lungo prefisso di $P$ che occorre in posizione 32 è composto da 4 simboli. Calcolare la successiva posizione della finestra e le posizioni dei simboli su $T$ e su $P$ da cui riparte il confronto. Spiegare il procedimento usato.
• Dare la definizione di funzione di fallimento per la ricerca esatta di un pattern $P$ in un teso $T$ tramite algoritmo KMP. In particolare, specificare il dominio e il codominio.
• Specificare e spiegare, aiutandosi con uno schema, la formula di caclolo del salto della finestra (dell’algoritmo KMP) durante la scansione del testo.
• Durante l’esecuzione dell’algoritmo KMP la finestra si trova in posizione 20 e il primo mismatch tra pattern e testo si trova in posizione 24 sul testo. Specificare la posizione sul testo da cui riparte il confronto dopo lo spostamento della finestra e perchè non si può derivare (con i dati a disposizione) la corrispondente posizione sul pattern (da cui riparte il confronto).
• La finestra $W$ dell’algoritmo di ricerca esatta KMP, per il pattern $P = acacaacca$ e un testo $T$, a un certo punto dell’esecuzione si trova in posizione 15 e il primo simbolo di mismatch con $T$ si trova in posizione 6 di $P$. Calcolare (mostrando il procedimento) la successiva posizione di $W$ su $T$.
• Sulla base della definizione di prefix-function, specificare la funzione $\varphi$ per il pattern $P = ababc$
• Per i pattern $P = ababc$ e $P'= acabc$, e solo in relazione al valore $\varphi(4)$, mostrate i passi di esecuzione dell’algoritmo di calcolo della prefix-function

SHIFT-AND (BYG e Wu-Mamber)

• Descrivere l’algoritmo di ricerca esatta di un pattern in un testo tramite il paradigma SHIFT-AND, cioè descrivere la fase di preprocessing e la fase di scansione.
• Dare la definizione di parola $D_i$ dell’algoritmo di ricerca esatta basato su paradigma SHIFT-AND. Specificare (1) quando la parola indica un’occorrenza e (2) come si ottiene la posizione di inizio di tale occorrenza.
• Con riferimento al pattern $P = aca$ e al testo $T = gtccata$ specificare (motivando la risposta) la parola $D_6$.
• Scegliere un testo e un pattern e fornire su di essi un esempio di parola $D_5^1$ di Wu e Mamber e spiegare cosa rappresenta.