Les multiples de 3 en binaire

Automates finis · niveau 3 (difficile)

Énoncé

Construire un automate qui, lisant un entier écrit en binaire (poids fort en tête, le bit 0 codé a, le bit 1 codé b), accepte ssi cet entier est multiple de $3$ .

Corrigé

(* é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 (2*r + b) mod 3 (décalage binaire). On accepte au reste 0. Par exemple "bb" code $1 1_{2} = 3$ : accepté. Un automate à trois états reconnaît ainsi une infinité de nombres — la puissance de la mémoire finie.

Énoncé

Corrigé

Exercices semblables