Ricordiamo le due assunzioni fatte in precedenza:
$$ \delta(j_{j-1}, T[i]) = j_i \iff P[1, j_i] = T[i-j_i+1, i] $$
$$ \delta(j_{j-1}, T[i]) = j_i \ \ \land\ \ j_i \leq j_{i-1} \implies j_i = |B(P[1, j_{i-1}]T[i])| $$
Durante la ricerca esatta del pattern acbdccbd con automa a stati finiti, si arriva allo stato 6 dopo avere letto un certo simbolo del testo. Specificare tale simbolo.
L’esecuzione per la ricerca esatta del pattern acbdacad con automa si trova allo stato 6. Che simbolo del testo viene letto dopo, se l’algoritmo passa allo stato successivo?
Dato il pattern dccdbcd, si può dire che l’esecuzione dell’automa su un determinato testo non arriva mai allo stato 0, dopo avere letto il simbolo d a partire da uno stato diverso da 0? In caso affermativo, specificare quali sono i possibili stati di arrivo.
Durante la ricerca esatta di un pattern $P$ con automa a stati finiti, si passa dallo stato 6 allo stato 4 dopo aver letto il simbolo g nel testo. Dimostrare che $P[1] = g$.
Dato il pattern accabaccba, l’automa arriva allo stato 4 dopo aver letto il simbolo $a$. Determinare i possibili stati di partenza.