Compter les mots acceptés

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.