Reconnaissance de motifs avec erreurs
un entier k, un motif p et un nom de fichier, et qui
motif à k erreur près au plus.
Les motifs considérés peuvent être de trois classes de difficulté
croissante. Je présente ici le cas le plus simple où le motif se réduit
Selon le cours, étant donné un motif p, on peut construire un automate
fini qui reconnaît l'ensemble des mots filtrés par le motif
Dans le cas simple ou le motif se réduit à un mot m =
un motif p à k erreurs près.
Dans un premier temps on pourra traiter le cas des motifs restreints à
Puis on considérera des motifs plus généraux,
Le motif « . » filtre n'importe quel caractère, tandis que
le motif « # » filtre n'importe quel mot.
Les motifs optionnels
Noté c?, ce motif filtre le mot vide et le mot formé de la
De même, le motif « .? » filtre le mot vide et tous les mots réduits
Il s'agit de compiler un motif en un automate non-déterministe,