Adloun

Contenir le motif ab

Exercice · OCaml (option informatique), chapitre 18 — Automates finis

Énoncé

Définir un automate reconnaissant les mots qui contiennent ab comme facteur.

Corrigé

let contient_ab = {
  nb_etats = 3; initial = 0;
  (* 0 : rien de prometteur ; 1 : on vient de lire un a ; 2 : ab vu (piège acceptant) *)
  acceptants = [| false; false; true |];
  delta = [| [| 1; 0 |];     (* 0 : a -> 1, b -> 0 *)
             [| 1; 2 |];     (* 1 : a -> 1 (reste prêt), b -> 2 (ab trouvé !) *)
             [| 2; 2 |] |];  (* 2 : on y reste, ab est déjà vu *)
}

L'état 1 mémorise « le dernier caractère est un a » ; y lire un b complète le motif et fait passer à l'état acceptant 2, dont on ne sort plus (état puits acceptant).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.