Reconnaissance de motifs avec erreurs

un entier k, un motif p et un nom de fichier, et qui affiche les lignes du fichier dont un sous-mot est filtré par le 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 Notez que cette relation entre les mots est symétrique et reflexive On dira que les mots m et m' diffèrent de au plus k erreurs, lorsqu'il existe k+1 mots e0, …, ek, avec

2.2  Reconnaissance des sous-mots

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 reconnaître les mots dont un sous-mot est filtré par p.
Dans le cas simple ou le motif se réduit à un mot m = L'ensemble des mots filtrés par m se réduit à m et reconnaître les sous-mots du texte qui diffèrent de m de au plus k détecter les lignes d'un texte dont un sous-mot est filtré par un 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,