Exercices (pc 9)
Exercice 1
Calculer un automate déterministe reconnaissant . Exercice 2
Donner d'abord un automate non-déterministe, puis un automate déterministe pour tester si le n-ième bit avant la fin dans une suite binaire est 1 ou 0. Exercice 3
Dans l'algorithme de Knuth, Morris et Pratt, on peut introduire une amélioration pour tenir compte du fait qu'en cas de discordance , on sait que a[i-j+1..i-1]=p[1..j-1], mais aussi que .
On modifie la fonction utilisée dans l'algorithme en posant h(i)=j si le plus long mot qui est à la fois préfixe et suffixe de p[1..i-1] et tel que de plus est de longueur j-1.
Pour p=abaab, on aura avec cette nouvelle définition
Comment faut il modifier les procédure init pour qu'elle calcule
cette nouvelle fonction h?