Exercices (pc 9)
Corrigé
Exercice 1
exo92mm39mm700 Exercice 2
nieme127mm43mm700L'automate non-déterministe L'automate déterministe a comme états les mots de longueur n avec les transitions pour , . Les états de l'automate déterminisé forment un codage de ces mots: on remplace 0 par i s'il est en i-ième position avant la fin et 1 par i' dans la même situation. Exercice 3
Il suffit de mettre
if p[i]<>p[j] then h[i]:=j else h[i]:=h[j];à la place de
h[i]:=j.