Langage non vide

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