Automates finis

let reconnait a symbole mot =
  let etat = ref a.initial in
  for i = 0 to String.length mot - 1 do
    etat := a.delta.(!etat).(symbole mot.[i])
  done;
  a.acceptants.(!etat)

let sym c = int_of_char c - int_of_char 'a'
(* reconnait termine_par_a sym "bba" = true ; ... "bab" = false *)

Sur "bba" : états $0\to 0\to 0\to 1$ (acceptant) $=$ true. Sur "bab" : $0\to 0\to 1\to 0$ (non acceptant) $=$ false.

let termine_par_a = {
  nb_etats = 2; initial = 0;
  acceptants = [| false; true |];
  delta = [| [| 1; 0 |]; [| 1; 0 |] |];
}

Lire a mène toujours à l'état 1 (acceptant), lire b à l'état 0 : l'état final reflète la dernière lettre.

let pair_de_a = {
  nb_etats = 2; initial = 0;       (* état = parité du nombre de a lus *)
  acceptants = [| true; false |];  (* 0 = pair (acceptant), 1 = impair *)
  delta = [| [| 1; 0 |];           (* depuis pair : a -> impair, b -> pair *)
             [| 0; 1 |] |];        (* depuis impair : a -> pair, b -> impair *)
}

Lire a bascule la parité (états 0 et 1), lire b la laisse. L'état acceptant 0 (pair) inclut le mot vide ($0$ occurrence, pair).

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).

let langage_non_vide a =
  let vu = Array.make a.nb_etats false in
  let nb_sym = Array.length a.delta.(0) in
  let rec visite e =
    if not vu.(e) then begin
      vu.(e) <- true;
      for s = 0 to nb_sym - 1 do visite a.delta.(e).(s) done
    end
  in
  visite a.initial;
  let trouve = ref false in
  for e = 0 to a.nb_etats - 1 do
    if vu.(e) && a.acceptants.(e) then trouve := true
  done;
  !trouve

Le langage est non vide si et seulement si un état acceptant est accessible depuis l'état initial dans le graphe des transitions. C'est un parcours en profondeur (chapitre 15) : l'automate est un graphe orienté.

let complement a = { a with acceptants = Array.map not a.acceptants }

Sur un AFD complet, inverser les états acceptants suffit : un mot est dans le complément ssi il n'était pas accepté. reconnait (complement termine_par_a) sym "bba" vaut false, et ... "bab" vaut true.

let intersection a b =
  let nb_sym = Array.length a.delta.(0) in
  let code p q = p * b.nb_etats + q in
  let n = a.nb_etats * b.nb_etats in
  let delta = Array.make_matrix n nb_sym 0 in
  let acceptants = Array.make n false in
  for p = 0 to a.nb_etats - 1 do
    for q = 0 to b.nb_etats - 1 do
      let e = code p q in
      acceptants.(e) <- a.acceptants.(p) && b.acceptants.(q);
      for s = 0 to nb_sym - 1 do
        delta.(e).(s) <- code a.delta.(p).(s) b.delta.(q).(s)
      done
    done
  done;
  { nb_etats = n; initial = code a.initial b.initial; acceptants; delta }

let les_deux = intersection termine_par_a pair_de_a

L'automate produit fait avancer les deux automates en parallèle ; un état est acceptant ssi ses deux composantes le sont. les_deux reconnaît l'intersection des deux langages.

let compte_mots a longueur =
  let nb_sym = Array.length a.delta.(0) in
  let nb = Array.make a.nb_etats 0 in
  nb.(a.initial) <- 1;
  for _i = 1 to longueur do
    let suivant = Array.make a.nb_etats 0 in
    for e = 0 to a.nb_etats - 1 do
      for s = 0 to nb_sym - 1 do
        let e' = a.delta.(e).(s) in
        suivant.(e') <- suivant.(e') + nb.(e)
      done
    done;
    for e = 0 to a.nb_etats - 1 do nb.(e) <- suivant.(e) done
  done;
  let total = ref 0 in
  for e = 0 to a.nb_etats - 1 do
    if a.acceptants.(e) then total := !total + nb.(e)
  done;
  !total

Programmation dynamique (chapitre 13) sur les états : nb.(e) compte les mots (de la longueur courante) menant à l'état e. À chaque lettre lue, on propage ces comptes le long des transitions. À la fin, on somme sur les états acceptants. Coût $\Theta (\text{longueur}\times n\times k)$ — sans énumérer les mots un à un.

(* état = reste modulo 3 du préfixe lu ; lire un bit b : reste := (2*reste + b) mod 3 *)
let mult3 = {
  nb_etats = 3; initial = 0;
  acceptants = [| true; false; false |];   (* reste 0 : multiple de 3 *)
  delta = [| [| 0; 1 |];      (* reste 0 : bit0 -> 0, bit1 -> 1 *)
             [| 2; 0 |];      (* reste 1 : bit0 -> 2, bit1 -> 0 *)
             [| 1; 2 |] |];   (* reste 2 : bit0 -> 1, bit1 -> 2 *)
}

L'état est le reste modulo $3$ de la valeur lue : lire un bit b transforme le reste r en (2r + b) mod 3 (décalage binaire). On accepte au reste 0. Par exemple "bb" code $11_2=3$ : accepté. Un automate à trois états reconnaît ainsi une infinité de nombres — la puissance de la mémoire finie*.

let equivalents a b longueur =
  let nb_sym = Array.length a.delta.(0) in
  let ok = ref true in
  let rec explore reste ea eb =
    if a.acceptants.(ea) <> b.acceptants.(eb) then ok := false;
    if reste > 0 then
      for s = 0 to nb_sym - 1 do
        explore (reste - 1) a.delta.(ea).(s) b.delta.(eb).(s)
      done
  in
  explore longueur a.initial b.initial;
  !ok

On fait avancer simultanément les deux automates (comme dans le produit) le long de tous les préfixes de longueur $\le$ longueur : à chaque étape, l'acceptation doit coïncider. Inutile de construire les mots — seuls comptent les deux états courants (ea, eb). Pour une équivalence exacte (toutes longueurs), on testerait le vide de intersection a (complement b) et réciproquement : l'équivalence des AFD est décidable.