Td automates en ligne Théorie des langages-télécharger ...

Théorie des langages : Td automates en ligne

Télécharger PDF

Option informatique

Corrigé : Automates en ligne (X 1998)

Partie I. Motifs et automates

Question 1.

a) Le motif c?ou filtre les mots "cou" et "clou" ; le motif c?ou*cou filtre tous les mots débutant par "ou" ou par "cou" et se terminant par "cou", à l’exception de "cou".

b) Le motif ** filtre le mot m= "abc" de deux façons différentes : - m1 = "a" et m2 = "bc" - m1 = "ab" et m2 = "c".

c) Raisonnons par récurrence sur la longueur |p| du motif p.

– Si |p| = 0, p est le motif vide, donc p1 et p2 aussi. Le mot m est nécessairement le mot vide, et il suffit de poser m1 = m2 = ε pour conclure.

– Si |p| > 0, supposons le résultat acquis aux rangs inférieurs. Si p1 est le motif vide, il suffit de poser m1 = ε et m2 = m pour conclure. Si p2 est le motif vide, on pose cette fois m1 = m et m2 = ε. On suppose désormais que p1 et p2 ne sont pas le motif vide, avec pour conséquence que p n’est pas un motif simple. Il se décompose donc sous la forme p = p3 p4, où p3 et p4 ne sont pas le motif vide, et puisque p filtre m, il existe une factorisation m = m3 m4 telle que p3 filtre m3 et p4 filtre m4.

Supposons |p1| ≤ |p3|. D’après le lemme de Levi, il existe un motif p' tel que p3 = p1 p' et p2 = p' p4. Par hypothèse de récurrence appliquée à p3, il existe une factorisation de m3 sous la forme : m3 = m1 m' telle que p1 filtre m1 et p' filtre m'. Mais alors p2 filtre le mot m' m4. Posons m2 = m' m4. Alors p1 p2 filtre le mot m1 m2 et m1 m2 = m1 m' m4 = m3 m4 = m. Le cas où |p3| ≤ |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 motif a??? 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) Si p est un motif simple, il est équivalent à α, * ou à α?, où α désigne une lettre quelconque de l’alphabet.

Les automates associés sont représentés comme suit : - A(α) : Un état initial et final avec une transition étiquetée par α. - A(*) : Un état initial et final avec une transition étiquetée par *. - A(α?) : Un état initial et final avec une transition étiquetée par α et une transition instantanée vers l’état initial.

b) Si p est le motif vide, l’automate A(∅) qui le reconnaît est l’automate vide.

c) Si p = p1 p2, soit A(p1) et A(p2) deux automates qui reconnaissent respectivement p1 et p2 et dont les états sont distincts. On construit l’automate A(p) en identifiant l’état final de A(p1) avec l’état initial de A(p2).

d) L’automate associé au motif c?ou*cou est représenté comme suit : - États : 0, 1, 2, 3, 4, 5, 6 - Transitions : - 0 → 1 étiquetée par c - 1 → 2 étiquetée par ε - 2 → 3 étiquetée par ou - 3 → 3 étiquetée par * - 3 → 4 étiquetée par c - 4 → 5 étiquetée par ou - 5 → 6 étiquetée par c - État final : 6

Question 3.

Commençons par observer que si a est un entier qui code un ensemble d’états A et α une lettre, alors bα = (a ∧ Nα) ⊕ 1 code l’ensemble des états atteints après une transition étiquetée par α.

Observons ensuite que b* = a ∧ N* code l’ensemble des états atteints après une transition étiquetée par *.

L’opérateur α(A) est donc représenté par l’entier b = bα ∨ b*.

Observons enfin que si b 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 : b0 = b et bi+1 = bi ∨ ((bi ∧ Nε) ⊕ 1). Cette suite est croissante donc stationnaire puisque majorée par 2n − 1, où n désigne le nombre d’états de l’automate. Sa limite A' représente l’ensemble des états ε(α(A)) = A'.

Partie II. Reconnaissance de motifs

Question 4.

a) Pour calculer plus aisément le code d’un caractère c dans le tableau alpha, on peut définir la fonction suivante : let indice c = int_of_char c − int_of_char 'a', qui indique l’indice i du tableau alpha où se trouve rangé l’entier Nc.

Les deux fonctions demandées peuvent être définies comme suit : let mange états c = let b1 = (états land alpha.(indice c)) lsl 1 and b2 = états land !etoile in b1 lor b2 let rec ferme états = let e = états lor ((états land !epsilon) lsl 1) in if états = e then e else ferme e

b) Toujours d’après cette même question, on obtient le code de l’état A' = ε(α(A)) à l’aide de la fonction : let etape états c = ferme (mange états c).

c) Sachant que les opérations sur les nombres entiers sont de coût constant, la fonction mange est de coût constant. Lorsque le motif p ne contient pas le caractère ?, le coût de la fonction etape est donc lui aussi constant.

Le coût de la fonction ferme est linéaire en le nombre de transitions instantanées consécutives présentes dans le motif p. Ce nombre est majoré par |p|, donc dans le cas général le coût de la fonction etape est un O(|p|).

d) La présence de l’état n−1 parmi l’ensemble d’états A représenté par l’entier b = (bi) est caractérisée par l’égalité bn−1 = 1. Sachant que 1 ⊕ (n−1) = (00...001 00...00), on définit la fonction : let etat_final états = états land (1 lsl (!n_etats − 1)) <> 0.

Question 5.

Pour respecter les spécifications de l’énoncé, on peut définir : exception Echec of string let echoue s = raise (Echec s).

a) Pour construire l’automate A(p), on parcourt les différents caractères qui composent p, en gardant en mémoire le dernier état ei créé.

Un caractère alphabétique α entraîne la création d’un nouvel état ei+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 suppose i > 1) ; dans les autres cas, il est ignoré.

Tout autre caractère déclenche l’exception Echec. Le nombre d’états est égal au nombre de caractères alphabétiques présents dans p, donc la référence n_etats est incrémentée à chaque fois qu’on en rencontre un.

La fonction de construction est : let construire_auto p = let rec aux i k = if k < string_length p then match p.[k] with | c when indice c >= 0 && indice c < 26 → incr n_etats ; 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) | '?' when k = 0 → echoue "motif invalide" | '?' when p.[k−1] = '?' || p.[k−1] = '*' → aux i (k + 1) | '?' → epsilon := !epsilon lor (1 lsl (i−1)) ; aux i (k + 1) | _ → echoue "motif invalide" in let alpha = Array.make 26 0 in let etoile = ref 0 and epsilon = ref 0 and n_etats = ref 1 in aux 0 0 ; (alpha, !etoile, !epsilon, !n_etats)

b) Chacune des opérations qui précède les appels récursifs à la fonction aux est de coût constant, donc le coût de cette construction est un O(|p|).

Question 6.

a) La fonction suivante construit l’automate associé au motif p, calcule à partir de l’ensemble d’états initiaux A0 = ε({e0}) l’ensemble d’états auquel on aboutit à la lecture du mot m, puis détermine si l’état final se trouve parmi eux : let filtre p m = let rec aux états = function | k when k = string_length m → etats | k → aux (etape états m.[k]) (k + 1) in let (alpha, etoile, epsilon, n_etats) = construire_auto p in etat_final (aux (ferme 1) 0)

b) Nous avons vu que le coût de la construction de l’automate est un O(|p|) et que le coût de la fonction etape est un O(1) s’il n’y a pas de motif optionnel, un O(|p|) sinon. On en déduit que le coût de la fonction filtre est un O(|p| + |m|) s’il n’y a pas de motif optionnel et un O(|p| · |m|) s’il en existe.

Question 7.

a) Posons q = *p* ; alors q filtre m si et seulement si p filtre un sous-mot de m. D’où la fonction : let filtre_sous_mot p = filtre ("*" ^ p ^ "*").

b) La lecture du préfixe mi de m aboutit à l’ensemble d’états Ai, donc p filtre mi si et seulement si l’état final de A(p) est dans Ai. Posons B0 = ε({e0}) et Bi+1 = ε(αi(Bi)) ∪ B0, et montrons par récurrence sur i que Bi est l’ensemble des états auquel peut aboutir la lecture d’un sous-mot de la forme mj...mi−1.

– Si i = 0, le sous-mot est vide et les états auquel on peut aboutir à partir de l’état e0 sont ε({e0}) = B0.

– Si i > 0, supposons le résultat acquis au rang i. Par hypothèse de récurrence, Bi est l’ensemble des états auquel aboutit la lecture d’un sous-mot mj...mi−1, donc