Théorie des langages : Td automates en ligne
Télécharger PDFoption informatique
Corrigé : automates en ligne (X 1998)
Partie I.
Motifs et automates
Question 1.
a)Le motifcl?oufiltre les mots "cou" et "clou" ; le motifc?ou* coufiltre tous les mots débutant par "ou" ou par "cou" et
se terminant par "cou" à l’exception de "cou".
b) Le motif** filtre le motm= "abc" de deux façons différentes, avecm1 = "a" etm2 = "bc" oum1 = "ab" etm2 = "c".
c) Raisonnons par récurrence sur la longueur|p|du motifp.
–Si|p|= 0,pest le motif vide, doncp1 etp2 aussi. Le motmest nécessairement le mot vide, et il suffit de poserm 1=m 2
=εpour conclure.
–Si|p|>0, supposons le résultat acquis aux rangs inférieurs. Sip1 est le motif vide il suffit de poserm1 =εetm 2
=mpour conclure. Sip2 est le motif vide on pose cette foism1 =metm2 =ε. On suppose désormais que nip 1nip 2
n’est le motif vide, avec pour conséquence quepn’est pas un motif simple. Il se décompose donc sous
la formep=p3 p4 où nip3 nip4 n’est le motif vide, et puisquepfiltremil existe une factorisationm=m3 m4 de
mtelle quep3 filtrem3 etp4 filtrem4 .
Supposons|p1 |6|p3 |. D’après le lemme deLeviil existe un motifp′ tel quep3 =p1 p′ etp2 =p′ p4 . Par hypothèse
de récurrence appliquée àp3 il existe une factorisation dem3 sous la forme :m3 =m1 m′ telle quep1 filtrem 1etp ′filtrem ′
. Mais alorsp2 filtre le motm′ m4 . Posonsm2 =m′ m4 . Alorsp1 p2 filtre le motm1 m2 etm 1m 2=m 1m ′m 4=m 3m 4=m. Le cas où|p3 |6|p1 |se traite de la même façon.
d) Les motifs* ?et** sont équivalents à* qui est de poids minimal puisque le motif vide ne filtre que le mot vide.
Le motifa???est équivalent àa?car ces deux motifs ne filtrent que les motsεet "a", et le second motif est de poids
minimal car aucun motif de poids égal à 1 ne peut filtrer ces deux mots et uniquement ceux-ci.
Question 2.
a)Sipest un motif simple il est équivalent àα,∗ou àα? oùαdésigne une lettre quelconque de l’alphabet, et les
automates associés sont représentés ci-dessous.01 α
Figure1 – L’automateA(α).0 ∗
Figure2 – L’automateA(∗).01 αε Figure3 – L’automateA(α?).
b) Sipest le motif vide, l’automateA(∅) qui le reconnait est l’automate vide.c) Sip=p1 p2 , soitA(p1 ) etA(p2 ) deux automates qui reconnaissent respectivementp1 etp2 et dont les états sont
distincts. On construit l’automateA(p) en identifiant l’état final deA(p1 ) avec l’état initial deA(p2 ) (ou en les reliant
par une transition instantanée).
d) Enfin, l’automate associé au motifc?ou* couest représenté ci-dessous.0123 456 cε ouc∗ ou
Figure4 – L’automateA(c?ou* cou).
page 1
Question 3.Commençons par observer que siaest un entier qui code un ensemble d’étatsAetαune lettre alorsb α
= (a∧Nα ) 1 code l’ensemble des états atteints après une transition étiquetée parα.
Observons ensuite queb∗ =a∧N∗ code l’ensemble des états atteints après une transition étiquetée par∗.
α(A) est donc représenté par l’entierb=bα ∨b∗ .
Observons enfin que sibi est un ensemble d’états,bi+1 =bi ∨((bi ∧Nε ) 1)code l’ensemble des états atteints après une
transition instantanée. Considérons donc la suite définie par :b 0=betb i+1=b i∨((b i∧N ε) 1) Cette suite est croissante donc stationnaire puisque majorée par2n −1 oùndésigne le nombre d’états de l’automate. Salimitea ′
représente l’ensemble des étatsε(α(A)) = A′ .
Partie II.
Reconnaissance de motifs
Question 4.Pour calculer plus aisément le code d’un caractèrecdans le tableaualphail peut être utile de définir la
fonction :
letindice c = int_of_char c−int_of_char ‘a‘ ;;
qui indique l’indiceidu tableaualphaoù se trouve rangé l’entier Nc .
a) D’après la question 3 les deux fonctions demandées peuvent être définies comme suit :
letmange états c =
letb1 = (états land (alpha.(indice c))) lsl 1andb2 = états land !etoilein
b1 lor b2 ;;
let recferme états =
lete = états lor ((états land !epsilon) lsl 1)in
ifétats = etheneelseferme e ;;
b) Toujours d’après cette même question, on obtient le code de l’état A′ =ε(α(A)) à l’aide de la fonction :
letetape états c = ferme (mange états c) ;;
c)Sachant que les opérations sur les nombres entiers sont de coût constant, la fonctionmangeest de coût constant.
Lorsque le motifpne contient pas le caractère?le coût de la fonctionetapeest donc lui aussi constant.
Le coût de la fonctionfermeest linéaire en le nombre de transitions instantanées consécutives présentes dans le
motifp. Ce nombre est majoré par|p|donc dans le cas général le coût de la fonctionetapeest un O(|p|).d) La présence de l’étaten−1 parmi l’ensemble d’étatsAreprésenté par l’entierb= (bi ) est caractérisé par l’égalitéb n−1
= 1. Sachant que 1 (n−1) = (00···001 00···00
︸ ︷︷ ︸n−1 )2 on définit la fonction :
letetat_final états = états land (1 lsl (!n_etats−1)) <> 0 ;;
Question 5.Pour respecter les spécifications de l’énoncé on peut définir :
exceptionEchecofstring ;;
letechoue s =raise(Echec s) ;;
a)Pour construire l’automateA(p) on parcourt les différents caractères qui composentpen gardant en mémoire le
dernier étatei créé.
Un caractère alphabétiqueαentraîne la création d’un nouvel étatei+1 et d’une transition alphabétique(ei , ei+1 ,α).
Un caractère∗entraîne la création d’une transition étoile(ei , ei ,∗). Un caractère?, s’il est précédé d’un caractère
alphabétique, entraîne la création d’une transition instantanée(ei , ei−1 ,ε) (ce qui supposei>1) ; dans les autres cas
il est ignoré. Tout autre caractère déclenche l’exceptionEchec.
Enfin, le nombre d’états est égal au nombre de caractères alphabétiques présents danspdonc la référencen_etats
est incrémentée à chaque fois qu’on en rencontre un.
page 2
letconstruire_auto p =
let recaux i k =
ifk <string_lengthpthen matchp.[k]with
| cwhenindice c >= 0 && indice c < 26−>
incr n_états ;
alpha.(indice c) <−alpha.(indice c) lor (1 lsl i) ;
aux (i+1) (k+1)
| ‘*‘−> etoile := !etoile lor (1 lsl i) ; aux i (k+1)
| ‘?‘whenk = 0−> echoue "motifinvalide"
| ‘?‘whenp.[k−1] = ‘?‘ || p.[k−1] = ‘*‘−> aux i (k+1)
| ‘?‘−> epsilon := !epsilon lor (1 lsl (i−1)) ; aux i (k+1)
| _−> echoue "motifinvalide"
infill_vect alpha 0 26 0 ;
etoile := 0 ; epsilon := 0 ; n_états := 1 ;
aux 0 0 ;;
b)Chacune des opérations qui précède les appels récursifs à la fonctionauxest de coût constant donc le coût de cette
construction est un O(|p|).
Question 6.
a)La fonction qui suit construit l’automate associé au motifp, calcule à partir de l’ensemble d’états initiauxA0 =ε({e0 })
l’ensemble d’états auquel on aboutit à la lecture du motm, puis détermine si l’état final se trouve parmi eux.
letfiltre p m =
let recaux états =function
| kwhenk =string_lengthm−> etats
| k−> aux (etape états m.[k]) (k+1)
inconstruire_auto p ; etat_final (aux (ferme 1) 0) ;;
b)Nous avons vu que le coût de la construction de l’automate est unO(|p|) et que le coût de la fonctionetapeest un
O(1)s’il n’y a pas de motif optionnel, unO(|p|) sinon. On en déduit que le coût de la fonctionfiltreest unO(|p|+|m|)
s’il n’y a pas de motif optionnel et un O(|p|·|m|) s’il en existe.
Question 7.
a) Posonsq=∗p∗; alorsqfiltremsi et seulement sipfiltre un sous-mot dem. D’où la fonction :
letfiltre_sous_mot p = filtre ("*" ^ p ^ "*") ;;
b)La lecture du préfixemi demaboutit à l’ensemble d’étatsAi doncpfiltremi si et seulement si l’état final deA(p) est
dans Ai .PosonsB 0=ε({e 0
}) etBi+1 =ε(αi (Bi ))∪B0 , et montrons par récurrence suriqueBi est l’ensemble des états auquel
peut aboutir la lecture d’un sous-motαj αj+1 ···αi−1 .
– Sii= 0 le sous-mot est vide et les états auquel on peut aboutir à partir de l’étate0 sontε({e0 }) = B0 .
–Sii>0 supposons le résultat acquis au rangi. Par hypothèse de récurrenceBi est l’ensemble des états auquel
aboutit la lecture d’un sous-motαj ···αi−1 doncε(αi (Bi )) est l’ensemble des états auquel aboutit la lecture d’un
sous-motnon videde la formeαj ···αi . Sachant queε({e0 }) =B0 est l’ensemble des états auquel aboutit la lecture
du sous-mot vide, on en déduit le résultat au rangi+ 1.
De ceci il résulte immédiatement qu’un sous-motαj ···αi−1 est filtré parpsi et seulement si l’état final deA(p)
appartient à Bi .
c)On construit l’automate associé au mot (qui est aussi un motif)spuis pour chaque valeur deion détermine si
un sous-mot demde la formemj ···mi−1 est reconnu par le motifs(notons que puisquesest uniquement formé
de caractères alphanumériques, un seul sous-mot de cette forme a une chance d’être reconnu, celui pour lequel
i−j=|s|).
Notons que puisqu’il n’y a pas de transition instantanée on a B0 ={e0 }et Bi+1 =αi (Bi )∪{e0 }.
page 3
letcompte_sous_mots s m =
construire_auto s ;
letb =ref1in
letnb =ref0in
fork = 0to string_lengthm−1do
b := etape !b m.[k] lor 1 ;
ifetat_final !bthenincr nb ;done; !nb ;;
d) Considérons le motifp=a?bet le motm=ab. L’automateA(p) est représenté ci-dessous :012 aε b
À la lecture du motmon aB0 ={0,1},B1 ={0,1}etB2 ={0,1,2}et seulB2 contient l’état final alors que deux
sous-mots demsont filtrés par le motifp:betab.
Question 8.
a)Pour détecter au plus un oubli il faut autoriser une transition instantanéeet une seuleentre deux états consécutifs de
A(μ). Ceci peut être représenté graphiquement en dupliquant les étatse1 , . . . , en−1 comme ci-dessous :012 n−1n 123n μ0 μ1 μn−1 μ1 μ2 εεεε
où on a notéμ=μ0 μ1 ···μn−1 les lettres deμ.
Considérons maintenant les lettresα0 ,α1 , . . . ,αk dem, et la suite d’états(Ai ) définie parA0 ={e0 }etAi+1 =αi (Ai ). Le
motmest reconnu sans erreur si et seulement sien ∈Ak (avec nécessairementk=n).
On pose ensuiteA1 0={e 1}etA 1i+1 =αi (A1 i
)∪succ(Ai ) oùsucc(Ai ) représente les successeurs des états contenus dansA i
. Alors le motmest reconnu avec un oubli si et seulement sien ∈A1 k
(avec cette foisk=n−1).
Le motmest donc reconnu avec au plus un oubli si et seulement sien ∈Ak ∪A1 k. b) Le cas d’une erreur quelconque peut être représenté par le diagramme ci-dessous :012 n−1n 0123n μ0 μ1 μn−1 μ0 μ1 μ2 ε, xε, xε, xε, xxxxx oùxreprésente un caractère quelconque. Les transitions(ei , ei , x) représentent des insertions, les transitions(ei , ei+1 , x)
des substitutions. La suite(A1 i
) doit être modifiée en posantA1 0={e 1}etA 1i+1 =αi (A1 i
)∪succ(Ai )∪Ai ∪succ(Ai+1 )
(le terme succ(Ai ) autorise un oubli, Ai une insertion, succ(Ai+1 ) une substitution).
c) Si l’ensemble d’états A est représenté par l’entiern, on a succ(A) =n 1. D’où la fonction :
letfiltre_erreur mu m =
construire_auto mu ;
leta =ref1anda1 =ref2in
fork = 0to string_lengthm−1do
letx = !ain
a := etape x m.[k] ;
a1 := (etape !a1 m.[k]) lor (x lsl 1) lor x lor (!a lsl 1)done; etat_final (!a lor !a1) ;;
page 4
d)Enfin, en combinant la démarche établie aux questions 7.b-c avec celle établie aux questions 8.b-c on obtient la
fonction :
letsous_mot_erreur mu m =
construire_auto mu ;
leta =ref1anda1 =ref2in
letrep =reffalsein
fork = 0to string_lengthm−1do
letx = !ain
a := etape x m.[k] lor 1 ;
a1 := (etape !a1 m.[k]) lor (x lsl 1) lor x lor (!a lsl 1) lor 2 ;
rep := !rep || etat_final (!a lor !a1)done; !rep ;;
page 5