Exercices (pc 9)

Exercice 1

Calculer un automate déterministe reconnaissant a^{∗}b^{∗}.

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 a[i] ≠ a[j], on sait que a[i − j + 1..i − 1] = p[1..j − 1], mais aussi que a[i] ≠ a[j].

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 p[i] ≠ p[j] est de longueur j − 1.

Pour p = abaab, on aura avec cette nouvelle définition

\begin{matrix}j & 1 & 2 & 3 & 4 & 5 \\ h(j) & 0 & 1 & 1 & 2 & 1 \end{matrix}

Comment faut il modifier les procédure init pour qu’elle calcule cette nouvelle fonction h?